题目描述

沙漠中有 $N$ 个补给站，编号为 $1$ 到 $N$。补给站之间有 $M$ 条双向公路，第 $i$ 条公路连接补给站 $U_i$ 和 $V_i$，长度为 $C_i$ 千米。

越野车的油箱加满后最多行驶 $L$ 千米。在任意补给站都可以选择将油箱加满，也可以不加油。每次加油都会直接将油箱加满，原来剩余的燃油不再保留。

共有 $Q$ 次询问。每次询问给出起点 $S_j$ 和终点 $T_j$，出发时油箱已经加满。请计算途中最少需要加油多少次；如果无法到达终点，输出 $-1$。出发前加满的一箱油不计入答案。

输入格式

第一行包含三个整数 $N,M,L$。

接下来 $M$ 行，每行包含三个整数 $U_i,V_i,C_i$，表示一条双向公路。

下一行包含一个整数 $Q$。

接下来 $Q$ 行，每行包含两个整数 $S_j,T_j$，表示一次询问。

输出格式

对于每次询问，输出一行一个整数，表示途中最少需要加油的次数；如果无法到达终点，输出 $-1$。

样例

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

0
1

数据范围与提示

• $2 \le N \le 300$
• $0 \le M \le \dfrac{N(N-1)}{2}$
• $1 \le L,C_i \le 10^9$
• $1 \le U_i,V_i,S_j,T_j \le N$
• $U_i \ne V_i$，$S_j \ne T_j$
• 不存在重边
• $1 \le Q \le N(N-1)$