1612 . Giant Snake
Description
In 5140 A.D., a giant snake appears in the subway system in an unknown city. The snake is so huge that it may put its head in one station and its tail in another. Furthermore, its body occupied all the tunnels along the path connecting the two stations. When a tunnel is occupied, nothing can get into this tunnel.
Although the mayor decided to abandon the subway system, you are unfortunately caught by the snake. You are asked to write a program for the snake, to help it figure out the shortest route to move its head to another station without crossing its body. If you successfully solve the snake's problem, you are free and the snake will give you a balloon. Otherwise, you will be eaten by the snake!
You have the map of the subway system. There are n stations, and some tunnels connecting two stations. Some of the tunnels may form a circular route, but no station belongs to two or more different routes. Also, no tunnel connects one station to itself, and no two tunnels connect the same pair of stations.
All tunnels are of equal length, and the snake has length l-0.5 tunnels. The snake can crawl along the tunnels, from one station to another station, in a head-first manner. The snake head cannot get into a station that is already occupied by its body.
Given the map, the initial position of the snake and the destination, please figure out what is the minimum number of tunnels that the snake has to crawl.
Input Format
The first line of the input file contains an integer T (T<=80), the number of test cases.
The first line of each test case consists of two integers, n and m (1<= n,m<= 100000), denoting the number of stations and the number of tunnels. Each of the following m lines contains two integers, a and b (1<= a,b<= n), denoting a tunnel connects station a and station b. The next line contains one integer l, characterizing the length of the snake. The following line contains l+1 integers, denoting the stations that the snake has occupied, starting from head. Note that the last station is not actually occupied by the snake, but is pointed by the tail. The input guarantees that the initial position of the snake is legal. The last line contains an integer, denoting the destination station which the snake wants to put its head.
Output Format
For each test case, please output the minimum number of tunnels if the snake can move its head to the destination. Otherwise please output -1.
Sample Input 1
1 6 6 1 2 2 3 3 4 4 5 5 2 4 6 2 5 2 3 1
Sample Output 1
4
Hints
Problem Source
Migrated from old NTUJ.
All-Russian Olympiad team programming 2010
Subtasks
| No. | Testdata Range | Score |
|---|