Вам даны \(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\)-я строка, — это \(p[mt_j]\). Разрешается не изменять порядок шаблонов.
Можно ли осуществить такое переупорядочивание? Если можно, то выведите любой корректный порядок.
Выходные данные
Выведите «NO», если невозможно переупорядочить шаблоны так, чтобы первый шаблон, под который подходит \(j\)-я строка, был \(p[mt_j]\).
В противном случае выведите «YES» в первой строке. Во второй строке выведите \(n\) различных целых чисел от \(1\) до \(n\) — порядок шаблонов. Если существует несколько ответов, выведите любой из них.
Примечание
Порядок шаблонов в первом примере после переупорядочивания:
Тогда первая строка подходит под шаблоны 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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 3 4
_b_d
__b_
aaaa
ab__
_bcd
abcd 4
abba 2
dbcd 5
|
YES
3 2 4 5 1
|
|
2
|
1 1 3
__c
cba 1
|
NO
|
|
3
|
2 2 2
a_
_b
ab 1
ab 2
|
NO
|