## Another Contest 2 Problem 3 - Poutine

View as PDF

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 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 contains 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