F. Слова на дереве
ограничение по времени на тест
9 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Дано дерево из $$$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$$$.

Найдите любой способ написать по одной букве на каждую вершину, чтобы соблюсти ограничения, или сообщите, что это невозможно.

Входные данные

В первой строке заданы два целых числа $$$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