Дано дерево из $$$n$$$ вершин, а также $$$q$$$ троек $$$(x_i, y_i, s_i)$$$, где $$$x_i$$$ и $$$y_i$$$ — целые числа от $$$1$$$ до $$$n$$$, а $$$s_i$$$ — строка, длина которой равна количеству вершин на простом пути от $$$x_i$$$ до $$$y_i$$$.
Вы должны написать на каждой вершине строчную латинскую букву таким образом, что для каждой из $$$q$$$ троек выполняется хотя бы одно из условий:
Найдите любой способ написать по одной букве на каждую вершину, чтобы соблюсти ограничения, или сообщите, что это невозможно.
В первой строке заданы два целых числа $$$n$$$ и $$$q$$$ ($$$2 \le n \le 4 \cdot 10^5$$$; $$$1 \le q \le 4 \cdot 10^5$$$) — количество вершин в дереве и троек, соответственно.
Затем следуют $$$n - 1$$$ строк; в $$$i$$$-й из них заданы два целых числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \ne v_i$$$) — концы $$$i$$$-го ребра. Эти ребра задают дерево.
Затем следуют $$$q$$$ строк; в $$$j$$$-й из них заданы два целых числа $$$x_j$$$ и $$$y_j$$$, а также строка $$$s_j$$$, состоящая из строчных латинских букв. Длина $$$s_j$$$ равна количеству вершин на простом пути между $$$x_j$$$ и $$$y_j$$$.
Дополнительное ограничение на входные данные: $$$\sum \limits_{j=1}^{q} |s_j| \le 4 \cdot 10^5$$$.
Если нет способа удовлетворить ограничения задачи, выведите NO. Иначе выведите YES в первой строке и $$$n$$$ строчных латинских букв во второй строке; $$$i$$$-я буква должна соответствовать той букве, которую вы пишете на $$$i$$$-й вершине. Если ответов несколько, выведите любой из них.
3 2 2 3 2 1 2 1 ab 2 3 bc
YES abc
3 2 2 3 2 1 2 1 ab 2 3 cd
NO
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
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
Название |
---|