Pattern Matching

题意翻译

### 题目描述 给定 $n$ 个模式串 $p_i$ 和 $m$ 个字符串 $s_i$，其中 $p_i$ 两两不同。每个模式串和字符串都包含 $k$ 个字符。其中模式串中可以含通配符（用下划线表示，可以匹配任何字符），剩余字符都为小写英文字母。同时给定 $n$ 个数 $mt_i$，要求重新排列模式串使得 $s_j$ 匹配到的第一个模式串为 $p_{mt_j}$。请判断是否存在排列方案满足如上要求，能的话请输出方案。 ### 输入格式 第一行三个正整数 $n,m,k$，分别表示模式串个数、字符串个数以及串长。 接下来 $n$ 行每行一个仅由小写英文字母与下划线组成的模式串 $p_i$。保证模式串串长为 $k$ 且两两不同。 接下来 $m$ 行每行一个字符串 $s_i$ 和一个正整数 $mt_i$。意义如题意表述。 ### 输出格式 如果存在方案，第一行输出 $\texttt{YES}$ 并在下一行输出 $n$ 个由空格分隔的整数表示模式串的顺序。 如果方案不存在，输出 $\texttt{NO}$ ### 数据范围 $1\le n,m\le 1\times 10^5$，$1\le k\le 4$，对于所有的 $mt$ 都有 $1\le mt\le n$。

题目描述

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.

输入输出格式

输入格式

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.

输出格式

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.

输入输出样例

输入样例 #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

说明

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 $ .