Escape from Heltion City

BaoBao, one of the most famous monster hunters, wakes up in the middle of Heltion City ruled by monsters. He starts at spot 1 and must reach one of the k exit spots to escape. The city is modeled as an undirected graph with n spots and m paths. However, each spot i is infested with d_i monsters. Whenever BaoBao arrives at spot i, at most d_i of the paths connected to that spot will be blocked by monsters (and the blocks can be chosen adversarially); once BaoBao leaves the spot, the paths are cleared, but if he revisits the same spot the blocking may occur again in an independent way.

To guarantee his escape in the worst‐case (that is, no matter which paths are blocked), BaoBao must have, at every intermediate spot, at least d_i+1 candidate paths so that even if the monsters block the d_i best ones, there is still one path available to proceed. Formally, if we denote by f(i) the minimum number of steps (each step traversing one path) required from spot i to an exit under an optimal strategy, then for any non‐exit spot i it is necessary that the set of neighbors j for which f(j) is finite has size at least d_i+1. In such a case we have:

$$f(i)=1+\min_{S\subseteq \{f(j): j\text{ is adjacent to } i\},\;|S|=d_i+1}\;\max S, $$

and for any exit spot e we define f(e) = 0.

Your task is to help BaoBao by computing the shortest time he can guarantee to escape the city in the worst‐case. If it is impossible to guarantee an escape, output -1.

inputFormat

The first line contains three integers n m k (n spots, m paths, and k exits).

The second line contains n integers: d1, d2, ..., dn, where di is the number of monsters at spot i.

The following m lines each contain two integers u and v (1-indexed) indicating an undirected path between spot u and spot v.

The last line contains k distinct integers e1, e2, ..., ek representing the exit spots.

outputFormat

Output a single integer: the minimum number of steps BaoBao must take to escape in the worst‐case scenario. If escape is impossible, output -1.

sample

2 1 1
0 0
1 2
2

1

</p>