Tattooed thugs P43809

Professor Oak is visiting a dangerous city. He wants to return to his hotel from a highlight of the city, but the streets have too many tattooed thugs. Therefore, Prof. Oak wants to reach the hotel always staying as far away from the thugs as possible.

The city can be represented as a set of junction and roads. The thugs are always located on junction points. From all the paths that go from the highlight to the hotel, which of them maximizes the minimum distance to the thugs?

Input

Input begins with the number of cases. Every case begins with the number of junctions n, the number of roads m and the number of thugs r. Follow m different pairs x y to indicate a bidirectional road between x and y. Follow the r different positions of the thugs. The junctions are numbered from 1 to n. The highlight is at 1 and the hotel is at n. There are never thugs at 1 or n. There is at least one path from 1 to n. Assume 3 ≤ n ≤ 10⁴, 2 ≤ m ≤ 5n and 1 ≤ r ≤ n − 2.

Output

Print the maximum distance to the thugs achievable by a path from the highlight to the hotel. Print “no thugs” if no thugs can reach Prof. Oak.