← 返回题目列表

Codeforces · 187/C

C. 记忆力弱

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

Zart PMP 获得参加中国哈尔滨 ICPC 世界总决赛的资格。团队游览太阳岛公园参加雪雕艺术博览会后,PMP 应在出发前返回巴士。但公园实在是太大了,他不知道怎么找到它们。

公园有 n 个交叉路口,编号为 1 到 n。有 m 条双向道路连接这些交叉路口中的一些对。在k个路口,ICPC志愿者正在为团队提供帮助,并为他们指路前往目的地。志愿者的地点是固定的、不同的。

当PMP询问志愿者去公交车站的路时,他/她可以告诉他整个路径。但公园里完全被冰雪覆盖,到处看起来都几乎一样。所以PMP只能记住每道题后最多q个路口(不包括他们当前站立的路口)。他总是告诉志愿者他的记忆力很差,如果没有长度(道路数量)最多为q的直接路径通向公交车站,志愿者将引导PMP到另一位志愿者(当然,他距离最多q个路口)。 ICPC 志愿者非常了解该地区,并且总是告诉 PMP 最好的方式。因此,如果有一条路可以到达公交车站,PMP 一定会找到它。

PMP 的初始位置是交叉路口 s,公交车在交叉路口 t。路口 s 总会有一名志愿者。你的工作是找出保证 PMP 能够找到总线的最小 q。

输入

第一行包含三个空格分隔的整数 n、m、k (2 ≤ n ≤ 105, 0 ≤ m ≤ 2·105, 1 ≤ k ≤ n) — 分别是十字路口、道路和志愿者的数量。下一行包含 k 个不同的空格分隔整数,介于 1 和 n 之间(含 1 和 n)——志愿者所在城市的数量。

接下来的 m 行描述道路。这些行中的第 i 行包含两个空格分隔的整数 ui, vi (1 ≤ ui, vi ≤ n, ui ≠ vi) — 第 i 条道路连接的两个交叉路口。任意两个交叉路口之间至多有一条道路。

输入的最后一行包含两个空格分隔的整数 s, t (1 ≤ s, t ≤ n, s ≠ t) — PMP 的初始位置和总线的位置。可能并不总是能够从 s 到达 t。

保证路口 s 处始终有志愿者。

输出

在唯一一行上打印问题的答案——保证 PMP 能够找到总线的 q 的最小值。如果 PMP 根本无法到达总线,则输出 -1。

示例

输入 #1

6 6 3
1 3 6
1 2
2 3
4 2
5 6
4 5
3 4
1 6

输出 #1

3

输入 #2

6 5 3
1 5 6
1 2
2 3
3 4
4 5
6 3
1 5

输出 #2

3

注意

第一个示例如下所示。蓝色十字路口是志愿者所在的地方。如果 PMP 沿着虚线路径行驶,它可以到达 q = 3 的总线:

在第二个样本中,PMP 使用交集 6 作为中间交集,因此答案为 3。