1476E - Pattern Matching - CodeForces Solution

from collections import deque
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def topological_sort():
    g = []
    q = deque()
    cnt = [0] * (n + 1)
    for i in range(1, n + 1):
        for j in G[i]:
            cnt[j] += 1
    for i in range(1, n + 1):
        if not cnt[i]:
            q.append(i)
    while q:
        i = q.popleft()
        g.append(i)
        for j in G[i]:
            cnt[j] -= 1
            if not cnt[j]:
                q.append(j)
    return g

n, m, k = map(int, input().split())
x = [1]
for _ in range(k - 1):
    x.append(27 * x[-1])
d = dict()
for v in range(1, n + 1):
    s = list(input().rstrip())
    u = 0
    for i, j in zip(x, s):
        u += i * max(0, j - 96)
    d[u] = v
pow2 = [1]
for _ in range(k):
    pow2.append(2 * pow2[-1])
l = pow2[k]
G = [[] for _ in range(n + 1)]
for _ in range(m):
    s, mt = input().rstrip().split()
    v = set()
    s, mt = list(s), int(mt)
    for i in range(l):
        u = 0
        for j in range(k):
            if i & pow2[j]:
                u += x[j] * (s[j] - 96)
        if u in d:
            v.add(d[u])
    if not mt in v:
        ans = "NO"
        print(ans)
        exit()
    for i in v:
        if i ^ mt:
            G[mt].append(i)
p = topological_sort()
ans = "YES" if not len(p) ^ n else "NO"
print(ans)
if ans == "YES":
    sys.stdout.write(" ".join(map(str, p)))