题目描述

有 $N$ 个编号为 $1$到 $N$ 的城镇以及 $M$ 条道路。

第$i$条道路以双向形式连接城镇 $A_i$和城镇 $B_i$，并且长度为 $C_i$。

高桥将乘车在这些城镇之间旅行，经过这些道路。他的汽车油箱最多能够容纳$L$升的燃料，每行驶单位距离需要消耗升燃料。

在旅行时拜访一个城镇时，他可以加满油箱(或选择不加油)。不能在路途的一半发现油箱变空的情况下旅 行。

处理以下 Q 个查询: 油箱现在是满的。从城镇 $s_i$ 到城镇 $t_i$ 旅行时，找到他需要加满油箱的最少次数。如果无法到达城镇$t_i$，输出 -1。

输入

第一行3个整数，表示$N,M,L$

接下来一共$M$行，表示$A_i,B_i,C_i$

接下来一个整数$Q$,表示询问次数

接下来一共$Q$行，每行两个整数$s_i,t_i$,表示第$i$组询问。

输出

第$i$行输出从城镇 $s_i$ 到城镇 $t_i$ 旅行时，加满油箱的最少次数。

如果无法到达城镇 $t$;，输出 -1。

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

0
1

样例解释

从城镇 3 到城镇 2，可以利用第二条道路在不加满油箱的情况下到达城镇 2.

从城镇 1 到城镇 3，可以先利用第一条道路到达城镇 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

提示

• $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$ )