F. XOR, деревья и запросы
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано дерево с $$$n$$$ вершинами. Вершины пронумерованы от $$$1$$$ до $$$n$$$.

Вам нужно будет назначить каждому ребру вес. Пусть вес $$$i$$$-го ребра будет $$$a_i$$$ ($$$1 \leq i \leq n-1$$$). Вес каждого ребра должен быть целым числом от $$$0$$$ до $$$2^{30}-1$$$, включительно.

Вам дано $$$q$$$ условий. Каждое условие состоит из трех целых чисел $$$u$$$, $$$v$$$ и $$$x$$$. Это означает, что побитовое исключающее ИЛИ всех ребер на кратчайшем пути от $$$u$$$ до $$$v$$$ должно быть равно $$$x$$$.

Выясните, существуют ли числа $$$a_1, a_2, \ldots, a_{n-1}$$$, удовлетворяющие заданным условиям. Если существуют, выведите такое решение, при котором $$$a_1 \oplus a_2 \oplus \ldots \oplus a_{n-1}$$$ будет наименьшим. Здесь $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ.

Если существует несколько решений таких, что $$$a_1 \oplus a_2 \oplus \ldots \oplus a_{n-1}$$$ является наименьшим, выведите любое из них.

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

Первая строка содержит два целых числа $$$n$$$ и $$$q$$$ ($$$2 \le n \le 2.5 \cdot 10^5$$$, $$$0 \le q \le 2.5 \cdot 10^5$$$). В $$$i$$$-й из следующих $$$n-1$$$ строк содержится два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$, $$$x_i \neq y_i$$$), то есть $$$i$$$-е ребро соединяет вершины $$$x_i$$$ и $$$y_i$$$ в дереве.

Гарантируется, что заданные ребра образуют дерево.

Следующие $$$q$$$ строк содержат информацию об условиях.

Каждая строка содержит три целых числа $$$u$$$, $$$v$$$, $$$x$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$, $$$0 \le x \le 2^{30}-1$$$), означающие, что побитовое исключающее ИЛИ всех ребер на кратчайшем пути от $$$u$$$ до $$$v$$$ должно быть $$$x$$$.

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

Если не существует $$$a_1$$$, $$$a_2$$$, ..., $$$a_{n-1}$$$, которые удовлетворяют заданным условиям, выведите «No».

В противном случае в первой строке выведите «Yes».

Затем в следующей строке выведите $$$n-1$$$ целых чисел, где $$$i$$$-е целое число — это вес $$$i$$$-го ребра. Если существует несколько решений, то выведите такое решение, при котором $$$a_1 \oplus a_2 \oplus \ldots \oplus a_{n-1}$$$ будет наименьшим.

Если существует несколько решений, при которых $$$a_1 \oplus a_2 \oplus \ldots \oplus a_{n-1}$$$ принимает наименьшее значение, выведите любое.

При выводе «Yes» или «No» вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Примеры
Входные данные
4 4
1 2
2 3
3 4
1 4 3
2 4 2
1 3 1
2 3 1
Выходные данные
No
Входные данные
6 2
1 2
2 3
3 4
2 5
5 6
1 4 2
2 6 7
Выходные данные
Yes
4 2 4 1 6
Входные данные
6 2
1 2
2 3
3 4
2 5
5 6
1 4 3
1 6 5
Выходные данные
Yes
6 1 4 3 0
Примечание

Для первого примера не существует набора весов ребер, удовлетворяющего заданному условию.

Для второго примера два условия означают, что $$$a_1 \oplus a_2 \oplus a_3=2$$$ и $$$a_4 \oplus a_5=7$$$. Может существовать несколько решений, например, $$$(a_1, a_2, a_3, a_4, a_5)=(1, 2, 1, 4, 3)$$$.

Для третьего примера два условия означают, что $$$a_1 \oplus a_2 \oplus a_3=3$$$ и $$$a_1 \oplus a_4 \oplus a_5=5$$$. Существует множество решений, удовлетворяющих данному условию.

$$$(a_1, a_2, a_3, a_4, a_5)=(1, 1, 3, 4, 0)$$$ удовлетворяет заданным условиям, но побитовое исключающее ИЛИ весов всех ребер равно $$$7$$$, что не является наименьшим возможным значением $$$a_1 \oplus a_2 \oplus \ldots \oplus a_{n-1}$$$, поэтому это не является верным решением.