Being an introvert at heart, Elon Musk, the french entrepeneur, has taken it upon himself to give the world yet another thing to marvel at: the Introverts Club. Since he is Elon Musk, the whole idea gained a lot of traction very quickly, and by now each major country has its own subsidiary of the Introverts Club. Ironically, people flock to the meetings in the thousands. While this does make everyone uncomfortable, nobody dares to complain, and so it comes that the German subsidiary decides to build the first stadium to house meetings in (just like Rock concerts, but without anyone saying anything).

The architects have already finished planning the stadium, but there is one requirement they had not thought of: to be allowed to house meetings of so many people, the stadium must have a minimum number of distinct escape routes. Being sort of a maze, it is not exactly clear whether the stadium as planned fulfills this requirement.

You are to write a program that, given the stadium's plans, solves this problem.


The input starts with the number \(1 \leq t \leq 100\) of test cases.

Each test case \(1 \leq i \leq c\) starts with the number of rooms in the stadium \(1 \leq r_i \leq 100\), followed by the number of rooms that count as safe spaces for people to escape to \(1 \leq er_i \leq r_i\) (these will usually be rooms that lead directly out of the stadium). \(er_i\) numbers between \(1\) and \(r_i\) follow that designate the escape rooms (you can assume that no room will appear twice).

Next up are the corridors that connect the rooms. A number \(0 \leq c \leq 1000\) specifies the number of corridors, and each corridor \(1 \leq j \leq c\) is specified through two numbers \(1 \leq s_j \neq t_j \leq r_i\). Each corridor can only be traversed in one direction, and you can assume that there are no direct bidirectional connections between a given pair of rooms.

Finally, there is an integer \(1 \leq d \leq 50\) that specifies how many escape routes are required for the stadium to be deemed safe enough.


For each test case, you are to output either safe or unsafe as there are or are not enough distinct escape routes from room 1 to any safe room. The escape routes may all lead to the same safe room, or to different safe rooms. Two routes are distinct if they share neither corridors nor rooms (except for the safe room they lead to). That is, if two escape routes lead through different corridors, but have one room along the routes in common, they cannot both be used as escape routes.

Sample Input


2 4 5
1 2
1 3
2 4
3 5

2 3 4
1 2
2 3
2 4

Sample Output


Upload Solution

Please log in to submit your solution.


Difficulty (0 votes)
Average test runtime 0.20
Points (changes over time) 10
Tried by 3 users
Solved by 1 user

Global ranking

# Name Runtime Points worth
1 Bjoern 0.20 10