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

题目：沙漠越野赛燃油补给问题

题目描述

一场精彩的沙漠越野赛即将在广袤沙漠中举行。沙漠中分布着 $N$ 个补给站（编号 $1$ 至 $N$ ），这些补给站通过 $M$ 条沙漠公路相连，公路为双向通行。其中第 $i$ 条公路连接补给站 $U_i$ 和 $V_i$ ，路程为 $C_i$ 公里。

参赛选手驾驶的越野车油箱容量为 $L$ 升，行驶 $1$ 公里消耗 $1$ 升燃油。当探险队抵达某个补给站时，可选择：

1. 在补给站将油箱加满。
2. 不加油，直接前往下一个补给站。

现有 $Q$ 个赛程，每个赛程指定从补给站 $S_j$ 出发前往目标补给站 $T_j$ 。若选手在行驶过程中燃油耗尽，当前赛程挑战失败（不影响后续赛程）并退出比赛。选手从出发补给站出发时，油箱已加满。

需计算对于每个赛程，选手若要挑战成功，从补给站 $S_j$ 到 $T_j$ 中途至少需补充燃油的次数（不含出发时加满的一箱油） 。若无论如何都无法抵达目的地，则输出 $-1$ 。

输入格式

1. 第一行：三个整数 $N$、$M$、$L$ ，分别表示补给站数量、公路数量、油箱容量。
2. 接下来 $M$ 行：每行三个整数 $U_i$、$V_i$、$C_i$ ，表示公路连接的两个补给站及公路长度。
3. 下一行：整数 $Q$ ，表示赛程数量。
4. 接下来 $Q$ 行：每行两个整数 $S_j$、$T_j$ ，表示每个赛程的出发补给站和目标补给站。

输出格式

输出 $Q$ 行，每行一个整数。第 $j$ 行数字表示从补给站 $S_j$ 到 $T_j$ 赛程中，选手至少需补给燃油的次数；若无法抵达则输出 $-1$ 。

样例

• 样例 1 输入

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

• 样例 1 输出

1
0

• 样例 1 说明
  • 沙漠有 $3$ 个补给站，$2$ 条公路：公路 $1$ 连接补给站 $1$ 与 $2$ ，长 $3$ 公里；公路 $2$ 连接补给站 $2$ 与 $3$ ，长 $3$ 公里。越野车油箱容量 $5$ 升，每公里耗油 $1$ 升，出发时油箱加满。
  • 从补给站 $3$ 到 $2$ 的赛程：选手可直接从补给站 $3$ 驶向补给站 $2$ ，耗油 $3$ 升，油箱剩余 $2$ 升，中途无需补给，输出 $0$ 。
  • 从补给站 $1$ 到 $3$ 的赛程：选手先从补给站 $1$ 驶向补给站 $2$ 耗油 $3$ 升，此时油箱剩 $2$ 升，而前往补给站 $3$ 还需 $3$ 升油，所以需在补给站 $2$ 补给一次将油箱加满才能继续行驶，输出 $1$ 。

数据范围

对于 $100\%$ 的数据，满足 $2 \leq N \leq 300$，$0 \leq M \leq \frac{N(N - 1)}{2}$，$1 \leq L \leq 10^9$，$1 \leq U_i, V_i \leq N$ 且 $U_i \neq V_i$ （每对 $U_i, V_i$ 不重复，即无重边），$1 \leq C_i \leq 10^9$，$1 \leq Q \leq N(N - 1)$，$1 \leq S_j, T_j \leq N$ 且 $S_j \neq T_j$ 。