You will be given a tree with node numbered 1 to with weighted edge.
You will be asked queries.
For each query you have to find the largest edge in path from to .
The first line contains two integers and (). Each of the next lines contains three integer , , , (, and ), meaning there is an edge between and with weight .
Each of the next lines contains two integer , ( and ) describing the query.
For each query. print the answer in a new line.
Input | Output |
---|---|
5 5 2 1 40 3 2 21 4 1 23 5 2 50 1 2 3 5 3 1 2 3 2 1 | 40 50 40 21 40 |
In query 1, from 1 to 2, there is only one edge and so the answer is 40. In query 2, from 3 to 5, largest edge in path is 2 -- 5 with weight 50, so the answer is 50. |
Input | Output |
---|---|
5 5 2 1 2 3 2 31 4 1 2 5 2 5 1 4 1 5 3 1 2 3 2 1 | 2 5 31 31 2 |