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^{4},
2 ≤ *m* ≤ 5*n* 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.

Public test cases

**Input**

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

**Output**

2 0 no thugs

Information

- Author
- Ivan Geffner
- Language
- English
- Official solutions
- C++
- User solutions
- C++
- Event
- Dotzè Concurs de Programació de la UPC - Semifinal
- Date
- 2014-07-02