Ivan's disqualification (2) P82299

Ivan had the great idea of dancing Gangnam Style in the middle of the ACM-ICPC World Finals, so he is going to be disqualified (again). The Big President himself will chase Ivan.

The Cosmos building, where this is happening, has multiple rooms (vertices) and corridors (undirected edges between different rooms). For every pair of rooms, there is at most one way to go from one to the other. Some rooms are exits to the outside. Initially, Ivan and BP are at different rooms. Every minute, both Ivan and BP can cross at most one corridor to move to an adjacent room.

Considering that both Ivan and BP move optimally, can you tell if Ivan is safe, and otherwise compute the maximum time that he can resist before being disqualified?

Input

Input begins with the number of cases. Each case begins with the number of rooms n, the number of corridors m and the number of exits r. Follow the initial position of Ivan and of BP. Follow m pairs x y indicating a corridor connecting rooms x and y. Follow the r exit rooms. Asume 2 ≤ n ≤ 10⁴, and that rooms are numbered from 1 to n.

Output

For every case, print the minute of Ivan’s disqualification. If BP cannot reach Ivan or if Ivan can escape to the outside print “safe”.