## Another Contest 2 Problem 3 - Poutine

View as PDF

Points: 15
Time limit: 0.6s
Java 8 1.0s
PyPy 3 2.0s
Memory limit: 256M

Problem types

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.

#### Input Specification

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 contain two space-separated positive integers, and , the parameters for query .

#### Output Specification

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 -1.

#### Sample Input

4
1 2 2
2 3 3
3 4 4
2
1 3
2 4

#### Sample Output

2
3