该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

徐老师正在进行一场别开生面的公路教学旅行，他打算驾车穿越全国各地的城镇，观察不同地区的学生学习状态。

假设徐老师需要旅行一共有 $N$ 个城镇，编号从 $1$ 到 $N$。这些城镇通过 $M$ 条双向公路连接，第 $i$ 条公路连接城镇 $A_i$ 和 $B_i$，长度为 $C_i$ 公里。

徐老师驾驶的教学车油箱容量为 $L$ 升，且每行驶 $1$ 公里消耗 $1$ 升油。在某个城镇停靠时，徐老师可以选择为油箱加满油，或者继续前行。

注意：车辆不能在出发途中下被困在路上！

你需要帮助徐老师判断他提出的 $Q$ 次旅行计划，每次询问如下：

• 起点城镇 $s_i$，终点城镇 $t_i$。
• 在起点出发时，油箱为空。
• 问：他从 $s_i$ 到 $t_i$ 的最少加油次数（包含出发前加满油），只有在油箱完全为空前加油才算一次。
• 如果根本无法到达 $t_i$，输出 -1。

约束

• 所有输入均为整数。
• $2 \leq N \leq 300$
• $0 \leq M \leq \dfrac{N(N-1)}{2}$
• $1 \leq L \leq 10^9$
• $1 \leq A_i, B_i \leq N$
• $A_i \neq B_i$
• $(A_i, B_i) \neq (A_j, B_j)$ (若 $i \neq j$)
• $(A_i, B_i) \neq (B_j, A_j)$ (若 $i \neq j$)
• $1 \leq C_i \leq 10^9$
• $1 \leq Q \leq N(N-1)$
• $1 \leq s_i, t_i \leq N$
• $s_i \neq t_i$
• $(s_i, t_i) \neq (s_j, t_j)$ (若 $i \neq j$)

输入格式

从标准输入读入数据，格式如下：

N M L
A1 B1 C1
:
AM BM CM
Q
s1 t1
:
sQ tQ

输出格式

输出共 $Q$ 行。

第 $i$ 行输出从城镇 $s_i$ 到城镇 $t_i$ 旅行时，加满油的最少次数。
如果无法到达，输出 -1。

输入输出样例

输入数据 1

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

输出数据 1

0
1

说明：

• 从城镇 3 到城镇 2，可以利用第二条道路在不加油的情况下到达。
• 从城镇 1 到城镇 3，可以先使用第一条道路到达城镇 2，加满油箱，然后利用第二条道路到达城镇 3。

输入数据 2

4 0 1
2
1 2
3 4

输出数据 2

-1
-1

说明：可能根本没有道路。

输入数据 3

5 4 4
1 2 2
2 3 2
3 4 3
4 5 2
20
1 2
2 1
1 3
3 1
1 4
4 1
1 5
5 1
2 3
3 2
2 4
4 2
2 5
5 2
3 4
4 3
3 5
5 3
4 5
5 4

输出数据 3

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