Description
One day, your friend Kirito traveled to a country called NTHU, which consists of n cities and n-1 roads. Each road has a cost associated with it.
In NTHU, there is a special rule: when you travel from city a to city b, the toll is only collected at the final destination, and it is determined by the highest toll of the roads you traveled on.
For example, if you passed through four roads with costs of 2, 4, 5, and 3, you would only be charged 5 units of currency, which is the highest toll on that path.
Kirito has listed many sightseeing route options. Can you help him calculate the toll for each of his proposed routes?
(Sample input)
Input
The first line contains two integers N and Q, where N ≤ 500000 and Q ≤ 1000000, representing the number of cities in the NTHU and the number of sightseeing routes.
The next N−1 lines each contain three numbers u, v, and w, indicating that there is an road with a toll w between city u and v.
Following this, there are Q lines, each containing two numbers a and b, indicating the query for the route from city a to b.
1 ≤ w ≤ 2147483647.
1 ≤ u, v, a, b ≤ N.
Output
The output consists of Q lines, each containing a single number that represents the highest toll on the route from city a to b.