Another Contest 2 Problem 3 - Poutine

View as PDF

Submit solution


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 N vertices.

Each trip has two parameters, a source vertex si and a destination vertex ti. 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 W1,,WK in nondecreasing order, he seeks to minimize WK1.

For each trip, compute this quantity.

Constraints

2N105

1ai,biN

1wi109

1Q105

1si,tiN

siti

Input Specification

The first line contains a single positive integer, N.

The next N1 lines contain three space-separated integers, ai, bi, and wi, indicating an undirected edge between ai and bi of weight wi.

The next line contains a single positive integer, Q.

The next Q lines contain two space-separated positive integers, si and ti, 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 si and ti using strictly fewer than two edges, output -1.

Sample Input

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

Sample Output

Copy
2
3

Comments

There are no comments at the moment.