驾车旅行

题目描述

有 $N$ 个编号为 $1$ 到 $N$ 的城镇和 $M$ 条道路。第 $i$ 条道路双向连接城镇 $A_i$ 和城镇 $B_i$，其长度为 $C_i$。

高桥君驾驶汽车在这些城镇之间移动。汽车油箱容量为 $L$ 升，每移动距离 $1$ 消耗 $1$ 升燃料。途中经过城镇时，可以将燃料补充至油箱加满（也可以选择不补充）。不能在道路中途耗尽燃料。

请回答以下 $Q$ 个查询。

• 开始时，汽车油箱是满的。从城镇 $s_i$ 移动到城镇 $t_i$ 时，途中至少需要补充几次燃料？如果无法移动到城镇 $t_i$，请输出 $-1$。

输入格式

输入按以下格式从标准输入给出：

$N$ $M$ $L$
$A_1$ $B_1$ $C_1$
$:$
$A_M$ $B_M$ $C_M$
$Q$
$s_1$ $t_1$
$:$
$s_Q$ $t_Q$

输出格式

输出 $Q$ 行。

第 $i$ 行输出从城镇 $s_i$ 移动到城镇 $t_i$ 时至少需要补充几次燃料。如果无法移动到城镇 $t_i$，输出 $-1$。

样例

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

0
1

从城镇 $3$ 移动到城镇 $2$ 时，使用第 $2$ 条道路即可不中途补充燃料到达城镇 $2$。

从城镇 $1$ 移动到城镇 $3$ 时，先使用第 $1$ 条道路移动到城镇 $2$，将燃料补充至油箱加满，再使用第 $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 \le N \le 300$
• $0 \le M \le \frac{N(N-1)}{2}$
• $1 \leq L \leq 10^9$
• $1 \le A_i, B_i \le 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 \le Q \le N\left(N-1\right)$
• $1 \le s_i, t_i \le N$
• $s_i \neq t_i$
• $\left(s_i, t_i\right) \neq \left(s_j, t_j\right)$（当 $i \neq j$ 时）