Processing math: 100%
Escape from... dolls - MarisaOJ: Marisa Online Judge

Escape from... dolls

Time limit: 1000 ms
Memory limit: 256 MB

Marisa is being chased by k Alice’s dolls. What Marisa has done to Alice, I will leave that to your imagination…

Marisa is now at vertex 1 of an connected, undirected graph of n vertices and m edges. The ith doll is at vertex Ai. Marisa and dolls can move to any adjacent vertex in 1 unit of time. The dolls always move optimally to chase Marisa.

Marisa can escape these dolls after reaching vertex n. If she encounters x dolls at a vertex (even at vertex n), she must fight them and they will stop chasing her. This action costs her x energy, but does not take time.

What is the minimum amount of energy she must spend to escape?

Input

  • The first line contains 3 integers n,m,k.
  • The second line contains k integers Ai.
  • The next m lines, each line contains 2 integers u,v, there is an edge between u and v.

Output

  • Print the minimum amount of energy Marisa must use to escape.

Constraints

  • 1≤n,m,k≤105.
  • 1≤u,v,Ai≤n.

Example

Input:

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

Output:

1

Note: She has to fight the second doll.