G. Любимая задача SlavicG-а
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задано взвешенное дерево с $$$n$$$ вершинами. Деревом называется неориентированный связный граф без циклов. Дерево является взвешенным, если каждому его ребру сопоставлено число — его вес. Дерево неориентировано, не содержит корня.

Так как деревья слишком скучны, вы решили повеселить себя игрой на дереве.

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

Вы начинаете игру, имея значение переменной $$$x$$$ равное $$$0$$$. Когда вы перемещаетесь по ребру $$$i$$$, то $$$x$$$ изменяет своё значение на $$$x ~\mathsf{XOR}~ w_i$$$ (где — $$$w_i$$$ вес $$$i$$$-го ребра).

Ваша задача пройти от вершины $$$a$$$ до вершины $$$b$$$, но вы имеете право входить в вершину $$$b$$$ только если $$$x$$$ после этого станет равно $$$0$$$. Другими словами, вы можете пройти по ребру $$$i$$$, которое ведёт в $$$b$$$ тогда и только тогда, когда $$$x ~\mathsf{XOR}~ w_i = 0$$$. Как только вы попадаете $$$b$$$, то игра заканчивается вашей победой.

Есть дополнительное правило — не более одного раза за игру вы можете воспользоваться телепортом. Он перемещает вас мгновенно в любую вершину (отличную от $$$b$$$). Вы можете использовать телепорт из любой вершины (даже из $$$a$$$).

Выведите «YES», если вы можете попасть в $$$b$$$ из $$$a$$$. Выведите «NO» в противном случае.

Операция $$$\mathsf{XOR}$$$ обозначает битовое исключающее ИЛИ.

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

Первая строка содержит единственное целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных в тесте.

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$a$$$ и $$$b$$$ ($$$2 \leq n \leq 10^5$$$), ($$$1 \leq a, b \leq n; a \ne b$$$) — количество вершин, а также начальную и конечную вершина, соответственно.

Каждая из следующих $$$n-1$$$ строк задает ребро дерева. Ребро $$$i$$$ задано тремя целыми числами $$$u_i$$$, $$$v_i$$$ и $$$w_i$$$  — метками вершин, которые оно соединяет ($$$1 \leq u_i, v_i \leq n; u_i \ne v_i; 1 \leq w_i \leq 10^9$$$) и своим весом.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

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

Для каждого набора входных данных выведите «YES», если вы можете достичь вершины $$$b$$$, и «NO» в противном случае.

Пример
Входные данные
3
5 1 4
1 3 1
2 3 2
4 3 3
3 5 1
2 1 2
1 2 2
6 2 3
1 2 1
2 3 1
3 4 1
4 5 3
5 6 5
Выходные данные
YES
NO
YES
Примечание

Для первого набора входных данных мы можем перейти от вершины $$$1$$$ в вершину $$$3$$$, при этом $$$x$$$ изменится с $$$0$$$ на $$$1$$$. Затем мы перейдем из $$$3$$$ в $$$2$$$, при этом $$$x$$$ станет равным $$$3$$$. Теперь мы можем телепортироваться в узел $$$3$$$ и переместиться из узла $$$3$$$ в узел $$$4$$$, достигнув узла $$$b$$$, так как в итоге $$$x$$$ стало равно $$$0$$$. Поэтому ответ равен «YES».

Во втором наборе входных данных пример у нас нет ходов, так как мы не можем телепортироваться к узлу $$$b$$$, а единственный ход, который у нас есть — это добраться до узла $$$2$$$, что невозможно, поскольку $$$x$$$ не будет равно $$$0$$$. Таким образом, ответ равен «NO».