Background

This problem is the easy version of P8201, and the solutions to the two problems are slightly different. The difference in the statement between this problem and P8201 is that this problem gives edge weights on the tree, not node weights.

Xiaozhi lives in “Chuanzhi Kingdom”, a country with $n$ cities, where the cities are connected by $n - 1$ roads.

Each road has a length $w_i$. We define the cost for Xiaozhi to walk from city $a$ to city $b$ as $\mathrm{dis}_{a, b} = \bigoplus \limits_{e \in \mathrm{path}\left(a, b\right)} w_e$, where $\bigoplus$ denotes bitwise XOR (if you do not know what bitwise XOR is, please refer to the hint/explanation below), and $\mathrm{path}\left(a,b\right)$ denotes the set of edges on the simple path from $a$ to $b$. In other words, $\mathrm{dis}_{a, b}$ is the result of taking all edges on the simple path between $a$ and $b$, written as $e_1, e_2, e_3, \dots$, and computing $w_{e_1} \bigoplus w_{e_2} \bigoplus w_{e_3} \dots$.

One day, Xiaozhi got a chance to participate in the Chuanzhi Cup. On his way to the contest venue, he thought of a problem, but it seems he cannot solve it, so he told you about it. Smart classmate, can you help him?

Problem Description

Xiaozhi said: “Since our country has only $n$ cities and $n - 1$ roads, then our country is equivalent to a tree. I was thinking: in our country, is there a city such that ‘the XOR of the cost to city $a$ and the cost to city $b$ equals $k$’? This is so hard. I cannot figure it out. Can you help me?”

That is, given cities $a, b$ and an integer $k$, please determine whether there exists a city $t$ such that $\mathrm{dis}_{t, a} \bigoplus \mathrm{dis}_{t, b} = k$.

Input Format

The first line contains two integers $n$, $m$, representing the number of cities in the country and the number of queries.

The next $n - 1$ lines each contain three integers $x, y, l$, indicating that there is an edge of length $l$ between city $x$ and city $y$.

The next $m$ lines each contain three integers $a, b, k$, indicating Xiaozhi walks from city $a$ to city $b$, and the meaning of $k$ is the same as in the problem description.

Output Format

Output $m$ lines, each containing one string.

For the $i$-th query, if there exists at least one city $t$ that satisfies the requirement, output Yes.

If there is no city that satisfies the requirement, output No.

The output is case-insensitive. For example, Yes, yES, YES, yes, etc. are all accepted as Yes.

5 3
1 2 2
1 3 6 
2 4 8
2 5 1
1 2 4
2 3 12
1 4 10

nO
No
YeS

5 10
2 1 63
3 1 57
4 2 2
5 2 84
5 2 84
4 1 9977404983223574764
2 5 84
2 1 15996060349666123522
5 4 86
3 1 8428615422876116375
5 1 107
2 3 6
2 3 6
4 2 2

yeS
nO
YEs
No
YEs
nO
YEs
yeS
yeS
YEs

Hint

Explanation of related concepts

“Tree”: A tree is an undirected simple connected graph with $n$ nodes and $n - 1$ edges.

“Bitwise XOR”: Bitwise XOR is the ^ operator in C++, python, and java. It is a binary operation. Compare the binary bits of two numbers bit by bit: if they are the same, the result bit is $0$; if they are different, the result bit is $1$. For example: $3 \bigoplus 5 = (011)_2 \bigoplus (101)_2 = (110)_2 = 6$. Note that this is a bitwise operation, not a logical operation.

Explanation for Sample 1

The figure below shows the map of Chuanzhi Kingdom.

For all $t \in \{1, 2, 3, 4, 5\}$, it is impossible to have $\mathrm{dis} _{t,1} \bigoplus \mathrm{dis}_{t, 2} = 4$ and $\mathrm{dis}_{t, 2} \bigoplus \mathrm{dis}_{t, 3} = 12$, so the output is No.

If we take $t = 5$, we have $\mathrm{dis}_{t, 1} \bigoplus \mathrm{dis}_{t, 4} = 10$, so the output is Yes.

Constraints

For all test points, it is guaranteed that $1 < n \leq 5 \times 10^5$, $1 \leq m \leq 5 \times 10^5$, $0 \leq w_i < 2^{64}$.

For each query, it is guaranteed that $1 \leq a, b \leq n$ and $a \neq b$, $0 \leq k < 2^{64}$.

Translated by ChatGPT 5