Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

You are given a tree with $N$ nodes. A non-negative weight is assigned to each edge of the tree.

Let’s denote $F(U, V)$ as the $\textbf{XOR}$ of all weights of the edges along the simple path connecting node $U$ and node $V$. The simple path is the path that visits each node at most once. $F(U, U) = 0$ for all $U$.

You’ll be given some queries. In each query, there will be two integers $U$ and $V$. You have to print the maximum value of $F(U, X)$, where $X$ is any node that lies on the simple path between node $U$ and node $V$.

A tree is an undirected connected graph with $N$ nodes and exactly $N-1$ edges. It has no cycles and there exists exactly one simple path between any pair of its nodes.

The $\textbf{XOR}$ operation is the bitwise xor operation represented with “$\oplus$” logic symbol, which is denoted as the "^" operator in C/C++/Java/Python.

The first line of the input will contain an integer $T$, the number of the test cases.

In each of the test cases, the first line will contain two integers $N, Q$, the number of nodes of the tree, and the number of queries. Each of the next $(N-1)$ lines will contain three integers $U, V, W (1\leq U, V\leq N; U\neq V; 0\leq W\leq10^9)$ denoting there is an undirected edge of $W$ weight between node $U$ and node $V$. Each of the next $Q$ lines will contain two integers $U$ and $V (1\leq U, V\leq N)$.

It is guaranteed that the given edges form a tree.

**Scoring**

Subtask 1 (10 Points):

$1\leq T\leq100$

$2\leq N, Q\leq 100$

Subtask 2 (20 Points):

$1\leq T\leq100$

$2\leq N, Q\leq 1000$

Subtask 3 (70 Points):

$1\leq T\leq5$

$2\leq N, Q\leq 10^5$

In each query, print the maximum value of $F(U, X)$ in a line, where $X$ is any node that lies on the simple path between node $U$ and node $V$.

Input | Output |
---|---|

2 3 4 2 1 17 2 3 10 3 2 3 1 1 2 1 2 4 4 3 1 11 2 3 14 2 4 19 2 2 3 3 1 1 3 4 | 10 27 17 17 0 0 0 29 |

73% Solution Ratio

Um_nikEarliest,

gryffindoFastest, 0.8s

gryffindoLightest, 88 MB

Deshi_TouristShortest, 2724B

Login to submit

Subtask 1: Any bruteforce solution should pass. Subtask 2: In each query(U,V)query(U, V)query(U,V), ...