分数: 6 点
问题陈述
高桥王国有 N 城镇和 M 道路。
城镇已编号 1,2,\ldots,N,以及 i第路 (1 \leq i \leq M) 连接城镇 u_i 和镇 v_i 双向。保证从一个城镇到另一个城镇,只要走几条路就可以到达。
此外,城镇中有加油站 a_1,a_2,\ldots,a_K.
答案 Q 查询。的 i第一个查询 (1 \leq i \leq Q) 如下。
- 求从城镇出发时需要穿过道路的最少次数 s_i 到镇 t_i 经过一个有加油站的城镇。
约束
- 2 \leq N \leq 2 \times 10^5
- 1 \leq M,Q \leq 2 \times 10^5
- 1 \leq K \leq \min(N-1,20)
- 1 \leq a_i \leq N
- a_i \neq a_j\,(i \neq j)
- 1 \leq u_i < v_i \leq N
- (u_i,v_i) \neq (u_j,v_j) \,(i \neq j)
- 1 \leq s_i , t_i \leq N
- 也不 s_i 也不 t_i 有一个加油站。
- 穿过一些道路可以从每个城镇到达每个城镇。
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M Q K a_1 a_2 \ldots a_K u_1 v_1 u_2 v_2 \vdots u_M v_M s_1 t_1 s_2 t_2 \vdots s_Q t_Q
输出
打印 Q 行。的 i第行 (1 \leq i \leq Q) 应包含以下问题的答案 i第一个查询。
示例输入 1
3 2 1 1 1 1 2 2 3 3 2
示例输出 1
3
进城后 3,我们可以去镇上 2, 镇 1, 镇 2 按照这个顺序用三个动作完成行程。用更少的步数是不可能做到的,所以我们打印 3.
示例输入 2
5 6 2 2 3 1 1 2 2 3 2 4 1 5 2 5 3 5 5 5 5 4
示例输出 2
2 3