Вам дано дерево с \(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}\) является наименьшим, выведите любое из них.
Выходные данные
Если не существует \(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» будут приняты как положительный ответ.
Примечание
Для первого примера не существует набора весов ребер, удовлетворяющего заданному условию.
Для второго примера два условия означают, что \(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}\), поэтому это не является верным решением.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 4
1 2
2 3
3 4
1 4 3
2 4 2
1 3 1
2 3 1
|
No
|
|
2
|
6 2
1 2
2 3
3 4
2 5
5 6
1 4 2
2 6 7
|
Yes
4 2 4 1 6
|
|
3
|
6 2
1 2
2 3
3 4
2 5
5 6
1 4 3
1 6 5
|
Yes
6 1 4 3 0
|