Background

Tasting the apples in heaven is nothing special. I want to taste the apples in hell.

Problem Description

In the darkness there are black flames, and only those with sharp eyes can catch them.

With this tiny bit of humble light, walk deep into hell...

Welcome to the judgment ground of hell.

$\texttt{hhpq.}$ has forced D into the judgment ground of hell. D must escape before a Flame Prison is successfully formed in the City of Karma Fire, so he wants to know how many seconds are left.

In this City of Karma Fire, there are $n$ altars and $m$ bidirectional roads along which flames can spread.

It is known that there are $k$ altars whose flames (fire seeds) have already been lit. Starting from the first second, the fire will begin to spread from the lit altars to altars that can be reached and are not yet lit.

Once an altar is lit, it is activated instantly, and it will connect a holy wall of karma fire to every altar that has a road to it.

When there exists a closed shape formed by these holy walls of karma fire, the Flame Prison is formed successfully.

Simplified statement

You are given an undirected graph with $n$ vertices and $m$ edges. Each vertex has a label. Initially, $k$ vertices have label 1 (their indices are given), and the remaining vertices have label 0.

Each second, for every vertex labeled 1, all vertices connected to it by an edge will have their labels changed to 1.

Find the minimum number of seconds needed so that the vertices labeled 1 together with the edges between adjacent 1-labeled vertices can form a simple cycle.

In other words, find the minimum number of seconds after which there exists a set of vertices labeled 1 that forms a simple cycle.

Input Format

The first line contains three positive integers: $n, m, k$.

The next $m$ lines each contain two positive integers: $x, y$ (altar $x$ and altar $y$ are connected by a karma-fire road).

The last line contains $k$ positive integers: the indices of the altars that have already been lit (have fire seeds).

Output Format

If D can escape, output how much time D has left.

Otherwise, if it is impossible to form a Flame Prison, output Poor D!.

3 3 1
1 2
2 3
3 1
1

1

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

Poor D!

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

Hint

Sample explanation

Sample 1 explanation

When time reaches the first second, the flame at altar $1$ spreads to altars $2$ and $3$. At this point, a closed shape has already been formed, so the answer is $1$.

Sample 2 explanation

It can be proved that no simple cycle can be formed in this case.

Constraints

Guarantees and notes

It is guaranteed that there are no multiple edges or self-loops in the graph.

It is guaranteed that the given graph is a connected undirected graph.

Help

The input size is large, so a fast input method is recommended.

Translated by ChatGPT 5