贝西正在农场里吃草,农场由 $$$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$$$。