E - 乘车出行

得分：500 分

问题描述

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

高桥将乘车在这些城镇之间旅行，经过这些道路。他的汽车油箱最多能够容纳 $L$ 升的燃料，每行驶单位距离需要消耗一升燃料。在旅行时拜访一个城镇时，他可以加满油箱（或选择不加油）。不能在路途的一半发现油箱变空的情况下旅行。

处理以下 $Q$ 个查询：

• 油箱现在是满的。从城镇 $s_i$ 到城镇 $t_i$ 旅行时，找到他需要加满油箱的最少次数。如果无法到达城镇 $t_i$，输出 $-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)$（若 $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 \leq Q \leq N\left(N-1\right)$
• $1 \leq s_i, t_i \leq N$
• $s_i \neq t_i$
• $\left(s_i, t_i\right) \neq \left(s_j, t_j\right)$（若 $i \neq j$）

输入

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

$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$。

从城镇 $1$ 到城镇 $3$，可以先利用第一条道路到达城镇 $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