問題文

$1$ から $N$ までの番号がついた $N$ 個の町と $M$ 本の道があります。$i$ 本目の道は町 $A_i$ と町 $B_i$ を双方向に結び、その長さは $C_i$ です。

高橋君はこれらの町の間を、道を車で通行することで移動します。車の燃料タンクの容量は $L$ リットルであり、距離 $1$ を移動する度に燃料を $1$ リットル消費します。移動中に町を訪れた場合、燃料をタンクが一杯になるまで補給することが出来ます (補給しないという選択も可能です)。道の途中で燃料が尽きるような移動は出来ません。

以下の $Q$ 個のクエリに答えてください。

• はじめ、車の燃料タンクは一杯です。町 $s_i$ から町 $t_i$ へ移動するとき、最小で何回途中で燃料を補給する必要があるかを答えてください。町 $t_i$ まで移動出来ない場合は $−1$ を出力してください。

制約

• 入力は全て整数
• $2 ≤ N ≤ 300$
• $0 ≤ M ≤ \\frac{N(N-1)}{2}$
• $1 \\leq L \\leq 10^9$
• $1 ≤ A_i, B_i ≤ N$
• $A_i \\neq B_i$
• $\\left(A_i, B_i\\right) \\neq \\left(A_j, B_j\\right)$ ( $i \\neq j$ のとき)
• $\\left(A_i, B_i\\right) \\neq \\left(B_j, A_j\\right)$ ( $i \\neq j$ のとき)
• $1 \\leq C_i \\leq 10^9$
• $1 ≤ Q ≤ N\\left(N-1\\right)$
• $1 ≤ s_i, t_i ≤ N$
• $s_i \\neq t_i$
• $\\left(s_i, t_i\\right) \\neq \\left(s_j, t_j\\right)$ ( $i \\neq j$ のとき)

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $L$ $A_1$ $B_1$ $C_1$ $:$ $A_M$ $B_M$ $C_M$ $Q$ $s_1$ $t_1$ $:$ $s_Q$ $t_Q$

出力

$Q$ 行出力せよ。

$i$ 行目には、町 $s_i$ から町 $t_i$ へ移動するとき、最小で何回燃料を補給する必要があるかを出力せよ。町 $t_i$ まで移動出来ない場合は $−1$ を出力せよ。

入力例 1

3 2 5
1 2 3
2 3 3
2
3 2
1 3

出力例 1

0
1

町 $3$ から町 $2$ へ移動するときは、 $2$ 本目の道を使えば、途中で燃料を補給することなく町 $2$ へ到着することが出来ます。

町 $1$ から町 $3$ へ移動するときは、まず $1$ 本目の道を使って町 $2$ へ移動し、燃料をタンク一杯まで補給し、 $2$ 本目の道を使うことにより、町 $3$ へ到着することが出来ます。

入力例 2

4 0 1
1
2 1

出力例 2

-1

道が無いこともあります。

入力例 3

5 4 4
1 2 2
2 3 2
3 4 3
4 5 2
20
2 1
3 1
4 1
5 1
1 2
3 2
4 2
5 2
1 3
2 3
4 3
5 3
1 4
2 4
3 4
5 4
1 5
2 5
3 5
4 5

出力例 3

0
0
1
2
0
0
1
2
0
0
0
1
1
1
0
0
2
2
1
0