Hurry the Hedgehog

Interview

Time limit5sMemory limit2048 MB

Summary

Find the shortest path from intersection 1 to n that uses only intersections with a Super Mushroom, and print its number of intersections.

Level: Easy3 of 10
Topics: BFS, Graph
Solved: No attempts yet

Problem

Hurry is a hedgehog who lives in the Mushroom Kingdom. He is on a mission to save Princess Plum from the evil Donkey Kong. To reach the Princess, Hurry must run through a hyperspace network of roads. These roads are dangerous. Each road he walks between two intersections exposes him to attacks from Space Invaders. Some intersections have a Super Mushroom that restores Hurry's health.

Find the shortest path through the network such that Hurry eats a Super Mushroom at every intersection on the path.

Input

The intersections are numbered from $1$ to $n$ . Hurry starts at intersection $1$ and must run to intersection $n$ .

The input is structured as follows:

One line with three integers: $1 \leq n \leq 10^5$ , the number of intersections; $0 \leq m \leq 10^6$ , the number of roads; and $1 \leq s \leq n$ , the number of Super Mushrooms.
One line with $\max(0, s-2)$ integers: the indices of the intersections that have a Super Mushroom. Intersections $1$ and $n$ always have a Super Mushroom and are not in this list.
$m$ lines with two integers each, indicating that there is a road between the two intersections with these indices.

Output

One line containing one integer: the number of intersections on the path Hurry has to run.

Examples2

Example 1
Input
```
6 6 5
3 4 5
1 2
2 6
1 3
3 4
4 5
5 6
```
Expected output
```
5
```

Example 2

Input

Expected output