题目描述

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

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

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

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

输入格式

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

$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$ を出力せよ。

题目大意

$n$ 个小镇，$m$ 条双向道路。第 $i$ 条道路从 $a_i$ 通向 $b_i$，长度为 $c_i$。车的油箱容量为 $L$，当行驶到一个镇上时可以选择加满油或者什么都不做。行驶单位长度的距离消耗一单位的油。

现在回答 $Q$ 个问题：

• 油箱现在为满，从 $s_i$ 到 $t_i$，最少需要加油多少次，或者输出无解。

$2\le n\le 300$，$0\le m\le n(n - 1)/2$，无重边，无自环。$1\le c_i, L\le 10^9$。

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

0
1

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

提示

制約

• 入力は全て整数
• $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$ のとき)

Sample Explanation 1

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

Sample Explanation 2

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