Fast Fingers Thomas is delivering poutine to Wilson's restaurants!
Fast Fingers Thomas will drive a truck on a weighted tree with vertices.
Each trip has two parameters, a source vertex and a destination vertex . Thomas does not like driving along long edges, so he seeks to minimize the length of the second-longest edge that he travels on. Formally, if the weights of the edges that Thomas traverses are in nondecreasing order, he seeks to minimize .
For each trip, compute this quantity.
The first line contains a single positive integer, .
The next lines contain three space-separated integers, , , and , indicating an undirected edge between and of weight .
The next line contains a single positive integer, .
The next lines contains two space-separated positive integers, and , the parameters for query .
Output lines. On the th line, output the length of the second-longest edge that Thomas will take for the th trip.
If Thomas can travel between and using strictly fewer than two edges, output
4 1 2 2 2 3 3 3 4 4 2 1 3 2 4