Another Contest 2 Problem 3 - Poutine

View as PDF

Submit solution


Points: 15
Time limit: 1.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 N vertices.

Each trip has two parameters, a source vertex s_i and a destination vertex t_i. 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 W_1, \dots, W_K in nondecreasing order, he seeks to minimize W_{K-1}.

For each trip, compute this quantity.

Constraints

2 \le N \le 10^5

1 \le a_i, b_i \le N

1 \le w_i \le 10^9

1 \le Q \le 10^5

1 \le s_i, t_i \le N

s_i \neq t_i

Input Specification

The first line contains a single positive integer, N.

The next N-1 lines contain three space-separated integers, a_i, b_i, and w_i, indicating an undirected edge between a_i and b_i of weight w_i.

The next line contains a single positive integer, Q.

The next Q lines contains two space-separated positive integers, s_i and t_i, the parameters for query i.

Output Specification

Output Q lines. On the ith line, output the length of the second-longest edge that Thomas will take for the ith trip. If Thomas can travel between s_i and t_i 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

Comments

There are no comments at the moment.