← 返回题目列表

AtCoder · past202112_k

K. 加油站

中文机器翻译题面 查看原题

分数: 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