CF1476E.Pattern Matching

You are given $n$ patterns $p_1, p_2, \dots, p_n$ and $m$ strings $s_1, s_2, \dots, s_m$. Each pattern $p_i$ consists of $k$ characters that are either lowercase Latin letters or wildcard characters (denoted by underscores). All patterns are pairwise distinct. Each string $s_j$ consists of $k$ lowercase Latin letters.

A string $a$ matches a pattern $b$ if for each $i$ from $1$ to $k$ either $b_i$ is a wildcard character or $b_i=a_i$.

You are asked to rearrange the patterns in such a way that the first pattern the $j$-th string matches is $p[mt_j]$. You are allowed to leave the order of the patterns unchanged.

Can you perform such a rearrangement? If you can, then print any valid order.

给你 $n$ 个模式 $p_1, p_2, \dots, p_n$ 和 $m$ 个字符串 $s_1, s_2, \dots, s_m$。每个模式 $p_i$ 由 $k$ 个字符组成，这些字符要么是小写拉丁字母，要么是通配符（用下划线 _ 表示）。所有模式两两互不相同。每个字符串 $s_j$ 由 $k$ 个小写拉丁字母组成。

字符串 $a$ 匹配模式 $b$，当且仅当对每个 $i$（从 $1$ 到 $k$），均有：$b_i$ 是通配符，或者 $b_i = a_i$。

你需要重新排列这些模式，使得第 $j$ 个字符串 $s_j$ 所匹配的第一个模式恰好是 $p[mt_j]$。你也可以选择保持模式的原始顺序不变（即不做任何重排）。

能否完成这样的重排？若可以，请输出任意一种合法的排列顺序。

The first line contains three integers $n$, $m$ and $k$ ($1 \le n, m \le 10^5$, $1 \le k \le 4$) — the number of patterns, the number of strings and the length of each pattern and string.

Each of the next $n$ lines contains a pattern — $k$ characters that are either lowercase Latin letters or underscores. All patterns are pairwise distinct.

Each of the next $m$ lines contains a string — $k$ lowercase Latin letters, and an integer $mt$ ($1 \le mt \le n$) — the index of the first pattern the corresponding string should match.

第一行包含三个整数 $n$、$m$ 和 $k$（$1 \le n, m \le 10^5$，$1 \le k \le 4$）—— 分别表示模式的数量、字符串的数量，以及每个模式和字符串的长度。

接下来的 $n$ 行中，每行包含一个模式 —— 由 $k$ 个字符组成，每个字符为小写拉丁字母或下划线 _。所有模式两两互不相同。

再接下来的 $m$ 行中，每行包含一个字符串 —— 由 $k$ 个小写拉丁字母组成，以及一个整数 $mt$（$1 \le mt \le n$）—— 表示该字符串应匹配的第一个模式的索引。

Print "NO" if there is no way to rearrange the patterns in such a way that the first pattern that the $j$-th string matches is $p[mt_j]$.

Otherwise, print "YES" in the first line. The second line should contain $n$ distinct integers from $1$ to $n$ — the order of the patterns. If there are multiple answers, print any of them.

如果无法重新排列这些模式，使得第 $j$ 个字符串所匹配的第一个模式为 $p[mt_j]$，则输出 "NO"。

否则，第一行输出 "YES"；第二行输出 $n$ 个互不相同的、取值范围为 $1$ 到 $n$ 的整数——即模式的排列顺序。若存在多个合法答案，输出任意一个即可。

The order of patterns after the rearrangement in the first example is the following:

• aaaa
• __b_
• ab__
• _bcd
• _b_d

Thus, the first string matches patterns ab__, _bcd, _b_d in that order, the first of them is ab__, that is indeed $p[4]$. The second string matches __b_ and ab__, the first of them is __b_, that is $p[2]$. The last string matches _bcd and _b_d, the first of them is _bcd, that is $p[5]$.

The answer to that test is not unique, other valid orders also exist.

In the second example cba doesn't match __c, thus, no valid order exists.

In the third example the order (a_, _b) makes both strings match pattern $1$ first and the order (_b, a_) makes both strings match pattern $2$ first. Thus, there is no order that produces the result $1$ and $2$.

第一个示例中重排后的模式顺序如下：

• aaaa
• __b_
• ab__
• _bcd
• _b_d

因此，第一个字符串依次匹配模式 ab__、_bcd、_b_d，其中最先匹配的是 ab__，即 $p[4]$。第二个字符串匹配 __b_ 和 ab__，其中最先匹配的是 __b_，即 $p[2]$。最后一个字符串匹配 _bcd 和 _b_d，其中最先匹配的是 _bcd，即 $p[5]$。

该测试用例的答案不唯一，其他合法的顺序也存在。

在第二个示例中，字符串 cba 不匹配 __c，因此不存在合法的顺序。

在第三个示例中，顺序 (a_, _b) 使得两个字符串均首先匹配模式 $1$；而顺序 (_b, a_) 则使得两个字符串均首先匹配模式 $2$。因此，不存在一种顺序能分别产生结果 $1$ 和 $2$。