← 返回题目列表

Codeforces · 1307/D

D. 牛和田野

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

贝西正在农场里吃草,农场由 $$$n$$$ 块田地组成,由 $$$m$$$ 双向道路连接。她目前在 $$$1$$$ 场地,并将在当天结束时返回位于 $$$n$$$ 场地的家。

谷仓奶牛联合会已命令农夫约翰安装一条额外的双向道路。该农场有 $$$k$$$ 特殊田地,他决定在两个不同的特殊田地之间安装道路。他可能会在两个已有道路直接连接的特殊领域之间添加道路。

添加道路后,Bessie 将沿着从田地 $$$1$$$ 到田地 $$$n$$$ 的最短路径回家。由于贝西需要更多的锻炼,农夫约翰必须最大化这条最短路径的长度。帮助他!

输入

第一行包含整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$n-1 \le m \le 2 \cdot 10^5$$$, $$$2 \le k \le n$$$) — 农场的田地数量,数量道路数量、特殊场地数量。

第二行包含 $$$k$$$ 整数 $$$a_1, a_2, \ldots, a_k$$$ ($$$1 \le a_i \le n$$$) — 特殊字段。所有 $$$a_i$$$ 都是不同的。

以下 $$$m$$$ 行中的第 $$$i$$$ 行包含整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$, $$$x_i \ne y_i$$$),表示字段 $$$x_i$$$ 和 $$$x_i$$$ 之间的双向道路$$$y_i$$$。

保证可以从所有其他字段到达任何字段。还保证对于任何一对字段,最多有一条道路连接它们。

输出

输出一个整数,即 Farmer John 最优安装一条路后,从字段 $$$1$$$ 到 $$$n$$$ 的最短路径的最大可能长度。

示例

输入 #1

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

输出 #1

3

输入 #2

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

输出 #2

3

注意

第一个示例的图表如下所示。特殊字段用红色表示。 Farmer John 的最佳选择是在田地 $$$3$$$ 和 $$$5$$$ 之间添加一条道路,得到的从 $$$1$$$ 到 $$$5$$$ 的最短路径长度为 $$$3$$$。

第二个示例的图表如下所示。 Farmer John 必须在田地 $$$2$$$ 和 $$$4$$$ 之间添加一条道路,生成的从 $$$1$$$ 到 $$$5$$$ 的最短路径长度为 $$$3$$$。