配点 : $500$ 点

問題文

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

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

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

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

制約

• 入力は全て整数
• $2 \leq N \leq 300$
• $0 \leq M \leq \frac{N(N-1)}{2}$
• $1 \leq L \leq 10^9$
• $1 \leq A_i, B_i \leq 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 \leq Q \leq N\left(N-1\right)$
• $1 \leq s_i, t_i \leq 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$ を出力せよ。

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

0
1

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

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

4 0 1
1
2 1

-1

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

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

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