Problem H: Nearest pair

Problem H: Nearest pair

Time Limit: 4 Sec  Memory Limit: 128 MB
Submit: 296  Solved: 63
[Submit][Status][Web Board]


Fred has a graph of n nodes and m undirected edges (the length of each edge is 1). These nodes are numbered from 1 to n. Now, he gives you a node set whose size is K. He asks you to calculate the shortest path between a node pair belonging to the node set.


The first line will be an integer T, which is the number of the test cases(1 <= T <= 10). For each test case, the first line will be three integers and n, m and K(1 <= n <= 300000, 1 <= m <= 400400, 1 <= K <= n). The following are m lines, and each line will be two integers x and y, which means that there is an undirected edge be x and y. The next line will be K unique integers , and each integer represents a node in the node set.


For each test, output the distance of the shortest path. If the path does not exist, then print-1  instead.

Sample Input

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

Sample Output