You are given a tree with nodes. A non-negative weight is assigned to each edge of the tree.
Let’s denote as the of all weights of the edges along the simple path connecting node and node . The simple path is the path that visits each node at most once. for all .
You’ll be given some queries. In each query, there will be two integers and . You have to print the maximum value of , where is any node that lies on the simple path between node and node .
A tree is an undirected connected graph with nodes and exactly edges. It has no cycles and there exists exactly one simple path between any pair of its nodes.
The operation is the bitwise xor operation represented with “” logic symbol, which is denoted as the "^" operator in C/C++/Java/Python.
The first line of the input will contain an integer , the number of the test cases.
In each of the test cases, the first line will contain two integers , the number of nodes of the tree, and the number of queries. Each of the next lines will contain three integers denoting there is an undirected edge of weight between node and node . Each of the next lines will contain two integers and .
It is guaranteed that the given edges form a tree.
Scoring
Subtask 1 (10 Points):
Subtask 2 (20 Points):
Subtask 3 (70 Points):
In each query, print the maximum value of in a line, where is any node that lies on the simple path between node and node .
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 |