Это была ночь перед рождеством, и пришло время Санте украсить свое Рождественское дерево. Это дерево состоит из \(n\) вершин, соединенных \(n-1\) ребром. На каждом ребре дерева расположена гирлянда, которую можно описать некоторым числом в двоичном представлении.
Посмотреть на это дерево собралось \(m\) эльфов. Каждый эльф выбрал две вершины \(a\) и \(b\), и он смотрит только на гирлянды на простом пути между этими вершинами. В результате созерцания у эльфа появляется любимое число, равное побитовому исключающему ИЛИ значений на ребрах этого пути.
Однако, Северный Полюс только начал восстанавливаться после недавней эпидемии ОРВИ. Из-за этого Санта успел забыть, как выглядели некоторые гирлянды, и проверить их он не может, потому что уже покинул Северный Полюс! К счастью, на помощь пришли эльфы: каждый из них сообщил Санте свою пару вершин \((a_i, b_i)\), и четность количества единичных битов в своем любимом числе. Другими словами, каждый эльф помнит, было ли количество \(1\)-ц в его любимом числе, записанном в двоичном виде, четным или нечетным.
Помогите Санте проверить, могло ли существовать такое дерево, и если да, как оно могло выглядеть, и возможно вы войдете в историю!
Выходные данные
Для каждого набора входных данных, сначала выведите YES или NO (в любом регистре), в зависимости от того, существует ли дерево, соответствующее памяти Санты, или нет.
Если ответ YES, выведите \(n-1\) строк по три целых числа в каждом: \(x\), \(y\) и \(v\) (\(1 \le x, y \le n\); \(0 \le v < 2^{30}\)) — ребро дерева и число, описывающее состояние гирлянды на нем. Множество ребер должно совпадать с множеством из входных данных, и если состояние гирлянды на ребре известно, то оно не должно измениться. Вы можете выводить ребра в любом порядке.
Если существует несколько решений, выведите любое.
Примечание
Первый набор входных данных соответствует изображению из условия.
Один из возможных ответов — это присвоить ребру \((1, 2)\) значение \(5\), а ребру \((2, 5)\) — значение \(3\). Этот способ подходит потому что:
- Первый эльф рассматривает путь между вершинами \(2\) и \(3\). Его любимое число будет равно \(4\), а потому он помнит значение \(1\) (так как в двоичном представлении \(4\) нечетное количество битов \(1\)).
- Второй эльф рассматривает путь между вершинами \(2\) и \(5\). Его любимое число будет равно \(3\), а потому он помнит значение \(0\) (так как в двоичном представлении \(3\) четное количество битов \(1\)).
- Третий эльф рассматривает путь между вершинами \(5\) и \(6\). Его любимое число будет равно \(7\), а потому он помнит значение \(1\) (так как в двоичном представлении \(7\) нечетное количество битов \(1\)).
- Четвертый эльф рассматривает путь между вершинами \(6\) и \(1\). Его любимое число будет равно \(1\), а потому он помнит значение \(1\) (так как в двоичном представлении \(1\) нечетное количество битов \(1\)).
- Пятый эльф рассматривает путь между вершинами \(4\) и \(5\). Его любимое число будет равно \(4\), а потому он помнит значение \(1\) (так как в двоичном представлении \(4\) нечетное количество битов \(1\)).
Заметим, что существуют и другие возможные ответы.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
6 5
1 2 -1
1 3 1
4 2 7
6 3 0
2 5 -1
2 3 1
2 5 0
5 6 1
6 1 1
4 5 1
5 3
1 2 -1
1 3 -1
1 4 1
4 5 -1
2 4 0
3 4 1
2 3 1
3 3
1 2 -1
1 3 -1
1 2 0
1 3 1
2 3 0
2 1
1 2 1
1 2 0
|
YES
1 2 0
1 3 1
2 4 7
3 6 0
2 5 0
YES
1 2 1
1 3 0
1 4 1
4 5 1
NO
NO
|