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.

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.

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