There are N halls in the dungeon connected by tunnels. In some halls there are robots that have simultaneously received a command to gather in one place.
The robots are arranged in such a way that, having received a command, they all begin to move at such a speed that the tunnel between any two halls is overcome in 1 minute. Robots cannot stop (including in the halls) and also change direction while in the tunnels (however, once in the hall, the robot can go out of it through the same tunnel through which it came to this hall).
Write a program that calculates the minimum time it takes for all the robots to get together (in a hall or in a tunnel).
Input
First, the numbers N — number of halls (1≤N≤400) and K — number of tunnels (1≤K≤20000). Next, K pairs of numbers are introduced, each pair describes the numbers of halls connected by a tunnel (you can move along the tunnel in both directions). There may be several tunnels between two halls. The tunnel can connect the hall to itself. This is followed by the number M (1≤M≤400) — the number of robots. Then M numbers are entered, specifying the numbers of the halls where the robots are located at the beginning. There can be several robots in one room.
Imprint
Print the minimum time in minutes after which the robots can get together. If the robots can never get together, print a single number –1 (minus one).
Examples
| # |
Input |
Output |
| 1 |
4 5
1 2
23
34
14
1 3
3
1 2 4
| 1 |
| 2 |
3 2
1 2
23
2
1 3
| 1 |