← 返回题目列表

Codeforces · 1476/E

E. 模式匹配

中文机器翻译题面 查看原题

给你 $$$n$$$ 模式 $$$p_1, p_2, \dots, p_n$$$ 和 $$$m$$$ 字符串 $$$s_1, s_2, \dots, s_m$$$。每个模式 $$$p_i$$$ 由 $$$k$$$ 字符组成,这些字符可以是小写拉丁字母或通配符(用下划线表示)。所有模式都是成对不同的。每个字符串 $$$s_j$$$ 由 $$$k$$$ 小写拉丁字母组成。

如果对于从 $$$1$$$ 到 $$$k$$$ 的每个 $$$i$$$,$$$b_i$$$ 是通配符或 $$$b_i=a_i$$$,则字符串 $$$a$$$ 与模式 $$$b$$$ 匹配。

系统会要求您重新排列模式,使 $$$j$$$ 字符串匹配的第一个模式是 $$$p[mt_j]$$$。您可以保持模式的顺序不变。

你能进行这样的重新排列吗?如果可以的话,请打印任何有效的订单。

输入

第一行包含三个整数 $$$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$$$) - 相应字符串应匹配的第一个模式的索引。

输出

如果无法重新排列模式以使第 $$$j$$$ 字符串匹配的第一个模式是 $$$p[mt_j]$$$,则打印“NO”。

否则,在第一行打印“YES”。第二行应包含从 $$$1$$$ 到 $$$n$$$ 的 $$$n$$$ 不同整数 - 模式的顺序。如果有多个答案,请打印其中任何一个。

示例

输入 #1

5 3 4
_b_d
__b_
aaaa
ab__
_bcd
abcd 4
abba 2
dbcd 5

输出 #1

YES
3 2 4 5 1

输入 #2

1 1 3
__c
cba 1

输出 #2

NO

输入 #3

2 2 2
a_
_b
ab 1
ab 2

输出 #3

NO

注意

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

- 啊啊啊
- __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$$$ 的顺序。