Дано дерево из \(n\) вершин, а также \(q\) троек \((x_i, y_i, s_i)\), где \(x_i\) и \(y_i\) — целые числа от \(1\) до \(n\), а \(s_i\) — строка, длина которой равна количеству вершин на простом пути от \(x_i\) до \(y_i\).
Вы должны написать на каждой вершине строчную латинскую букву таким образом, что для каждой из \(q\) троек выполняется хотя бы одно из условий:
- если выписать буквы на пути от \(x_i\) до \(y_i\) в том порядке, в котором они встречаются на пути, вы получите строку \(s_i\);
- если выписать буквы на пути от \(y_i\) до \(x_i\) в том порядке, в котором они встречаются на пути, вы получите строку \(s_i\).
Найдите любой способ написать по одной букве на каждую вершину, чтобы соблюсти ограничения, или сообщите, что это невозможно.
Выходные данные
Если нет способа удовлетворить ограничения задачи, выведите NO. Иначе выведите YES в первой строке и \(n\) строчных латинских букв во второй строке; \(i\)-я буква должна соответствовать той букве, которую вы пишете на \(i\)-й вершине. Если ответов несколько, выведите любой из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
2 3
2 1
2 1 ab
2 3 bc
|
YES
abc
|
|
2
|
3 2
2 3
2 1
2 1 ab
2 3 cd
|
NO
|
|
3
|
10 10
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 2 ab
1 3 ab
1 4 ab
1 5 ab
1 6 ab
1 7 ab
1 8 ab
1 9 ab
1 10 ab
10 2 aba
|
YES
baaaaaaaaa
|
|
4
|
10 10
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 2 ab
1 3 ab
1 4 aa
1 5 ab
1 6 ab
1 7 ab
1 8 ab
1 9 ab
1 10 ab
10 2 aba
|
NO
|