A15509 | SlavicG's Favorite Problem

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 ~\mathsf{XOR}~ 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 ~\mathsf{XOR}~ 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 $\mathsf{XOR}$ represents the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).

The first line contains a single integer $t$ ( $1 \leq t \leq 1000$ ) — the number of test cases.

The first line of each test case contains three integers $n$ , $a$ , and $b$ ( $2 \leq n \leq 10^5$ ), ( $1 \leq a, b \leq n; a \ne b$ ) — 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 \leq u_i, v_i \leq n; u_i \ne v_i; 1 \leq w_i \leq 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$ .

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