User's AC Ratio

90.0% (9/10)

Submission's AC Ratio

53.3% (24/45)

Description

貝西正在草地吃草,農地由 $n$ 塊草地及 $m$ 條雙向邊組成;她現在在第 $1$ 塊草地,這天結束時,她要回家,而她家在第 $n$ 塊草地。

上頭命令農夫約翰要再蓋一條雙向邊。該農地有 $k$ 塊特殊草地,他決定在兩個不同的特殊草地之間蓋這條邊,若是草地間本來就有邊,也可以蓋上去。
蓋完邊後,貝西將從第 $1$ 草地以最短路徑走到第 $n$ 草地。由於貝西需要更多的運動,因此農夫約翰必須盡可能增加這條最短路徑的長度。

Input Format

第 1 列有 3 個正整數 $n, m, k$ 表示有 $n$ 塊草地及 $m$ 條雙向邊,還有 $k$ 塊特殊草地 ($2≤n≤2\cdot 10^ 5, n−1≤m≤2\cdot 10^ 5, 2≤k≤n$)

第 2 列有 $k$ 個不同的數字,表示特殊草地的編號

接著有 $m$ 列 $x$ 及 $y$ 表示第 $x$ 草地與第 $y$ 草地之間有雙向邊 ($1≤x,y≤n, x≠y$)

保證點與點間至多只有一條邊,且圖為連通圖。

Output Format

輸出在農夫約翰蓋完邊後,這條從第 $1$ 草地到第 $n$ 草地最短路徑的最大可能長度。

Sample Input 1

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

Sample Output 1

4

Sample Input 2

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

Sample Output 2

3

Hints

範例 1 的圖長這樣

由於重複蓋在已有的邊上也可以,所以 $(2, 3), (2, 4), (3, 5)$ 都可以蓋
但是蓋 $(4, 5)$ 的話最短路徑是 $2$,所以不會蓋 $(4, 5)$

(目前測資頗弱,謹慎練習)

Problem Source

Codeforces 1307D Cow and Fields

Subtasks

No. Testdata Range Score
1 0~19 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 1
2 1000 65536 65536 1
3 1000 65536 65536 1
4 1000 65536 65536 1
5 1000 65536 65536 1
6 1000 65536 65536 1
7 1000 65536 65536 1
8 1000 65536 65536 1
9 1000 65536 65536 1
10 1000 65536 65536 1
11 1000 65536 65536 1
12 1000 65536 65536 1
13 1000 65536 65536 1
14 1000 65536 65536 1
15 1000 65536 65536 1
16 1000 65536 65536 1
17 1000 65536 65536 1
18 1000 65536 65536 1
19 1000 65536 65536 1