Another Contest 2 Problem 3 - Poutine

View as PDF

Submit solution


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

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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.