問題文

Penguinman は木で遊ぶのが大好きです。

ここに $N$ 頂点の木があります。$i$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を双方向に結び、長さは $w_i$ です。以下のクエリが $Q$ 個与えられるので、順に処理してください。

• 頂点 $x$ で始まって頂点 $y$ で終わり、また以下の条件を共に満たすような、要素の重複を許す頂点列の中で $2$ 番目に長さが短いものの長さを求めて出力してください。そのような頂点列が存在しない場合は代わりに $-1$ を出力してください。

  1. $i$ 番目の頂点と $i+1$ 番目の頂点が直接辺で結ばれている　$(1≤i≤($頂点列のサイズ$-1))$
  2. $i$ 番目の頂点と $i+1$ 番目の頂点を結ぶ辺のうち、同じものは $2$ 度までしか現れない。

また、長さが同じでも頂点列として異なれば区別することとします。

入力

$N$
$u_1\ v_1\ w_i$
:
$u_{N-1}\ v_{N-1}\ w_{N-1}$
$Q$
$x_1\ y_1$
$︙$
$x_Q\ y_Q$

便宜上 $i$ 番目のクエリにおける $x,y$ をそれぞれ $x_i,y_i$ としています。

入力は以下の制約を満たすことが保証されます。

• $2≤N≤10^5$
• $1≤Q≤10^5$
• $1≤u_i,v_i≤N(1≤i≤N-1)$
• $1≤w_i≤10^9(1≤i≤N-1)$
• $1≤x_i,y_i≤N(1≤i≤Q)$
• $u_i≠v_i(1≤i≤N-1)$
• $x_i≠y_i(1≤i≤Q)$
• 与えられるグラフは木
• 入力は全て整数

出力

$i$ 行目には $i$ 番目のクエリに対する答えを出力してください。

サンプル

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

11
-1

5
1 4 10
2 3 100
1 2 38
1 5 2
4
1 2
2 3
3 4
1 4

42
176
152
14

6
1 3 19
1 2 20
1 4 1
5 1 10
4 6 8
5
1 2
3 4
5 3
6 2
3 1

22
36
31
49
21