「DAOI R1」Flame
题目背景
>尝尝天堂里的苹果有什么了不起,我要尝尝地狱里的苹果。
题目描述
黑暗里有黑色的火焰,只有目光敏锐的人才可以捕捉到,
借着这点卑微之光,走进地狱深处......
欢迎来到地狱的审判之地。
$ \texttt{hhpq.} $ 将 D 押入了地狱的审判之地,D 必须在业火之城成功生成一座业火监狱之前逃离,所以他想知道还有多少秒时间。
在这座业火之城中,共有 $n$ 个祭坛,共有 $m$ 条可以蔓延火苗的业火之路,且业火之路是双向连通。
已知在这一座业火之城共有 $k$ 个火种已被点燃的业火祭坛,且从第一秒开始,火种将开始从被点燃的业火祭坛向可以蔓延且未被点燃的业火祭坛蔓延。
当祭坛被点燃后,则会瞬间激活,和与之有路的祭坛连接业火圣壁。
当存在一片由业火圣壁构成的封闭图形时,则业火监狱生成成功。
### 简化题意
给出一个 $n$ 个点,$m$ 条边的无向图,每一个点有一个标记,初始有 $k$ 个点的标记为 `1`(将给出这 $k$ 个点的编号),其余的点标记为 `0`。
每一秒,对于每个标记为 `1` 的点,与它**有边相连**的点的标记都会变成 `1`。
求最少需要多少秒,图中标记为 `1` 的点与其相邻的边可以构成一个简单环。
**换言之,求最少多少秒后存在一个由 `1` 构成的集合形成简单环。**
输入输出格式
输入格式
第一行三个正整数:$n,m,k$;
下面 $m$ 行,每行两个正整数:$x,y$(第 $x$ 座业火祭坛与第 $y$ 座业火祭坛有业火之路连接);
最后一行 $k$ 个正整数:已被点燃(拥有火种)的祭坛编号。
输出格式
若可以逃离,输出 D 还有多少时间。
反之若无法生成业火监狱,输出 ``` Poor D! ```。
输入输出样例
输入样例 #1
3 3 1
1 2
2 3
3 1
1
输出样例 #1
1
输入样例 #2
5 4 2
1 2
2 3
3 4
2 5
1 5
输出样例 #2
Poor D!
输入样例 #3
15 15 2
2 1
2 3
2 9
5 9
4 5
5 7
6 7
7 8
7 11
11 10
10 9
10 14
14 15
11 12
12 13
4 15
输出样例 #3
3
说明
### 样例解释
#### 样例1解释
当时间到第一秒时,祭坛 $1$ 的火焰将蔓延到祭坛 $2$ 和 $3$,此时已经构成一个封闭图形了,故答案为 $1$。
#### 样例2解释
可以证明到此时是无法产生简单环的。
### 数据规模
| Subtask | $n\leq$ | $m\leq$ | $k\leq$ | 分值 |
| :----------: | :----------: | :----------: | :----------: | :----------: |
| $0$ | $10^6$ | $n-1$ | $10^4$ | $5$ |
| $1$ | $10^6$ | $2\times10^6$ | $1$ | $10$|
| $2$ | $10$ | $45$ | $1$ | $5$ |
| $3$ | $200$ | $500$ | $10$ | $10$ |
| $4$| $2\times 10^3$ | $5\times 10^3$ | $50$ | $10$ |
| $5$ | $5\times10^5$ | $6\times10^5$ | $500$ | $30$ |
| $6$ | $10^6$ | $2\times10^6$ | $10^4$ | $30$ |
### 保证与约定
保证数据无重边和自环;
保证数据给定的图是一张无向连通图。
### 帮助
输入量较大,建议使用较为快速的读入方式。