（travelbycar.cpp 2s/1024MB）

题目描述

这里有$N$个城镇，编号从$1$到$N$和$M$条道路，第$i$条道路连接$A_i$和$B_i$,并且长度为$C_i$。
T先生想要用骑车去旅行。他的油箱最多装$L$升油，其中每升油恰好能走路的长度为$1$.T先生可以在任意城镇进行补油，将油箱填满。 这里有$Q$个询问，每次给定起点$s_i$和终点$t_i$,若T先生不能从$s_i$顺利到达$t_i$（半路上没油了），则输出-1。否则输出最少的补油次数。（在起点满油）。

输入格式

第一行三个整数N,M,L
接下来M行每行三个整数$A_i,B_i,C_i$。
下一行一个整数Q。 接下来一个Q行每行两个整数$s_i,t_i$。

输出格式

共Q行，每一行针对每个询问输出答案。

样例

输入样例

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

输出样例

0
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)$(if $i\ \neq\ j$ )
• $\left(A_i,\ B_i\right)\ \neq\ \left(B_j,\ A_j\right)$(if $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$
  30%的数据满足：
• $2\ \leq\ N\ \leq\ 100$