Олимпиадный тренинг

Задача . F. Слова на дереве


Задача

Темы: Деревья *2600 поиск в глубину и подобное графы 2-sat снм

Дано дерево из \(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\)-й вершине. Если ответов несколько, выведите любой из них.


Примеры
№Входные данныеВыходные данные
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

time 9000 ms
memory 1024 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++5
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет