CF187C.Weak Memory

普及+/提高

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Zart PMP is qualified for ICPC World Finals in Harbin, China. After team excursion to Sun Island Park for snow sculpture art exposition, PMP should get back to buses before they leave. But the park is really big and he does not know how to find them.

The park has n intersections numbered 1 through n. There are m bidirectional roads that connect some pairs of these intersections. At k intersections, ICPC volunteers are helping the teams and showing them the way to their destinations. Locations of volunteers are fixed and distinct.

When PMP asks a volunteer the way to bus station, he/she can tell him the whole path. But the park is fully covered with ice and snow and everywhere looks almost the same. So PMP can only memorize at most q intersections after each question (excluding the intersection they are currently standing). He always tells volunteers about his weak memory and if there is no direct path of length (in number of roads) at most q that leads to bus station, the volunteer will guide PMP to another volunteer (who is at most q intersections away, of course). ICPC volunteers know the area very well and always tell PMP the best way. So if there exists a way to bus stations, PMP will definitely find it.

PMP's initial location is intersection s and the buses are at intersection t. There will always be a volunteer at intersection s. Your job is to find out the minimum q which guarantees that PMP can find the buses.

扎特·PMP 获得了在中国哈尔滨举行的 ICPC 世界总决赛的参赛资格。在团队参观完太阳岛公园的冰雪雕塑艺术展后,PMP 需要在大巴车离开前赶回乘车点。但公园非常大,他不知道该如何找到大巴车。

公园共有 nn 个路口,编号为 11 到 nn。有 mm 条双向道路连接其中某些路口对。在 kk 个路口处,有 ICPC 志愿者为各参赛队提供帮助,并指引他们前往目的地。志愿者的位置是固定的,且互不相同。

当 PMP 向某位志愿者询问前往公交站(即大巴车停靠点)的路线时,该志愿者会告诉他整条路径。但由于整个公园被冰雪完全覆盖,处处看起来几乎一模一样,因此 PMP 每次提问后最多只能记住 qq 个路口(不包括他当前所处的路口)。他总会向志愿者说明自己记忆力较弱;若不存在一条长度(以道路数量计)不超过 qq 的直达路径通向公交站,则志愿者会引导 PMP 前往另一位志愿者处(当然,这位志愿者也必须位于至多 qq 条道路距离之内)。ICPC 志愿者对该区域极为熟悉,总能为 PMP 指出最优路径。因此,只要存在通往公交站的路径,PMP 就一定能找到。

PMP 的初始位置是路口 ss,而大巴车位于路口 tt。初始位置 ss 处必定有一位志愿者。你的任务是求出保证 PMP 能够成功找到大巴车的最小 qq 值。

输入格式

The first line contains three space-separated integers n, m, k (2 ≤ n ≤ 105, 0 ≤ m ≤ 2·105, 1 ≤ k ≤ n) — the number of intersections, roads and volunteers, respectively. Next line contains k distinct space-separated integers between 1 and n inclusive — the numbers of cities where volunteers are located.

Next m lines describe the roads. The i-th of these lines contains two space-separated integers u__i, v__i (1 ≤ u__i, v__i ≤ n, u__i ≠ v__i) — two intersections that i-th road connects. There will be at most one road between any two intersections.

Last line of input contains two space-separated integers s, t (1 ≤ s, t ≤ n, s ≠ t) — the initial location of PMP and the location of the buses. It might not always be possible to reach t from s.

It is guaranteed that there is always a volunteer at intersection s.

第一行包含三个以空格分隔的整数 nn、mm、kk(2 ≤ n ≤ 1052 \leq n \leq 10^5,0 ≤ m ≤ 2⋅1050 \leq m \leq 2\cdot10^5,1 ≤ k ≤ n1 \leq k \leq n)——分别表示交叉路口数量、道路数量和志愿者数量。
下一行包含 kk 个互不相同的、在 11 到 nn 之间的以空格分隔的整数——表示志愿者所在的城市编号。

接下来 mm 行描述道路。其中第 ii 行包含两个以空格分隔的整数 uiu_i、viv_i(1 ≤ ui, vi ≤ n1 \leq u_i, v_i \leq n,ui ≠ viu_i \neq v_i)——表示第 ii 条道路所连接的两个交叉路口。任意两个交叉路口之间至多存在一条道路。

输入的最后一行包含两个以空格分隔的整数 ss、tt(1 ≤ s, t ≤ n1 \leq s, t \leq n,s ≠ ts \neq t)——分别表示 PMP 的初始位置和公交车的位置。从 ss 出发不一定总能到达 tt。

保证交叉路口 ss 上始终有一名志愿者。

输出格式

Print on the only line the answer to the problem — the minimum value of q which guarantees that PMP can find the buses. If PMP cannot reach the buses at all, output -1 instead.

在唯一的一行上输出该问题的答案——保证 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

说明/提示

The first sample is illustrated below. Blue intersections are where volunteers are located. If PMP goes in the path of dashed line, it can reach the buses with q = 3:

In the second sample, PMP uses intersection 6 as an intermediate intersection, thus the answer is 3.

第一个样例图示如下。蓝色交点为志愿者所在位置。若PMP沿虚线路径行进,则可到达满足 $ q = 3 $ 的公交车:

在第二个样例中,PMP以交点6作为中转交点,因此答案为3。

输入解题思路,AI测评打分。不知道怎么写?

首页