← Home
write a go solution for Description:
You are given a weighted tree with n vertices. Recall that a tree is a connected graph without any cycles. A weighted tree is a tree in which each edge has a certain weight. The tree is undirected, it doesn't have a root.

Since trees bore you, you decided to challenge yourself and play a game on the given tree.

In a move, you can travel from a node to one of its neighbors (another node it has a direct edge with).

You start with a variable x which is initially equal to 0. When you pass through edge i, x changes its value to x~mathsfXOR~w_i (where w_i is the weight of the i-th edge).

Your task is to go from vertex a to vertex b, but you are allowed to enter node b if and only if after traveling to it, the value of x will become 0. In other words, you can travel to node b only by using an edge i such that x~mathsfXOR~w_i=0. Once you enter node b the game ends and you win.

Additionally, you can teleport at most once at any point in time to any vertex except vertex b. You can teleport from any vertex, even from a.

Answer with "YES" if you can reach vertex b from a, and "NO" otherwise.

Note that mathsfXOR represents the bitwise XOR operation.

Input Format:
The first line contains a single integer t (1<=t<=1000) — the number of test cases.

The first line of each test case contains three integers n, a, and b (2<=n<=10^5), (1<=a,b<=n;aneb) — the number of vertices, and the starting and desired ending node respectively.

Each of the next n-1 lines denotes an edge of the tree. Edge i is denoted by three integers u_i, v_i and w_i  — the labels of vertices it connects (1<=u_i,v_i<=n;u_inev_i;1<=w_i<=10^9) and the weight of the respective edge.

It is guaranteed that the sum of n over all test cases does not exceed 10^5.

Output Format:
For each test case output "YES" if you can reach vertex b, and "NO" otherwise.

Note:
For the first test case, we can travel from node 1 to node 3, x changing from 0 to 1, then we travel from node 3 to node 2, x becoming equal to 3. Now, we can teleport to node 3 and travel from node 3 to node 4, reaching node b, since x became equal to 0 in the end, so we should answer "YES".

For the second test case, we have no moves, since we can't teleport to node b and the only move we have is to travel to node 2 which is impossible since x wouldn't be equal to 0 when reaching it, so we should answer "NO".. Output only the code with no comments, explanation, or additional text.