题目描述
Problem Background
It's no big deal to taste the apples in heaven; I want to taste the apples in hell.
Problem Description
In the darkness, there are black flames that only sharp-eyed individuals can catch.
With this meager light, venture deep into the heart of hell...
Welcome to the judgment ground of hell.
$\texttt{hhpq.}$ has brought D into the judgment ground of hell, where D must escape before a prison of hellfire is successfully generated. Therefore, he needs to know how many seconds remain.
In this city of hellfire, there are $n$ altars and $m$ paths for the flames to spread, and these paths are bidirectional.
It is known that there are $k$ altars already ignited with fire seeds, and from the first second, the fire seeds will start spreading from the ignited altars to adjacent, unignited altars.
Once an altar is ignited, it will instantly activate and connect with adjacent altars through a sacred wall of hellfire.
When a closed figure formed by these sacred walls exists, the prison of hellfire is successfully generated.
Simplified Problem Statement
Given an undirected graph with $n$ nodes and $m$ edges, each node has a flag. Initially, $k$ nodes have their flags set to 1 (the numbers of these $k$ nodes will be provided), and the rest have their flags set to 0.
Each second, for each node with a flag of 1, the flags of all its adjacent nodes will be set to 1.
Determine the minimum number of seconds required for the nodes with a flag of 1 and their adjacent edges to form a simple cycle.
In other words, find the minimum number of seconds after which a simple cycle is formed by the set of nodes with a flag of 1.
Input Format
The first line contains three positive integers: $n, m, k$.
The next $m$ lines each contain two positive integers: $x, y$ (indicating that the $x$-th altar and the $y$-th altar are connected by a path of hellfire).
The last line contains $k$ positive integers: the numbers of the altars that are already ignited (have fire seeds).
Output Format
If D can escape, output how many seconds D has left.
Otherwise, if a prison of hellfire cannot be generated, output Poor D!.
Sample Input and Output
Sample Input #1
3 3 1
1 2
2 3
3 1
1
Sample Output #1
1
Sample Input #2
5 4 2
1 2
2 3
3 4
2 5
1 5
Sample Output #2
Poor D!
Sample Input #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
Sample Output #3
3
Notes
Sample Explanation
Sample 1 Explanation
When the time reaches the first second, the flame from altar $1$ will spread to altars $2$ and $3$, forming a closed figure, hence the answer is $1$.
Sample 2 Explanation
It can be proven that at this point, a simple cycle cannot be formed.
Data Size
| Subtask | $n\leq$ | $m\leq$ | $k\leq$ | Score |
|---|---|---|---|---|
| $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$ |
Guarantees and Conventions
The data guarantees no duplicate edges or self-loops;
The data guarantees that the provided graph is a connected undirected graph.
Help
Due to the large input size, it is recommended to use a fast input method.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分