Marcos the little one decided to build and manage an espionage agency, he was happy working as the chief of his agency, hiring spies to spy everybody in the country! But he realized that some of their own spies are spying themselves, of course, this is bad to the business and he don't want this to happen, he wants a program to alert him whenever a spy is spying another spy.

Input

Will consists in T test cases, then, T cases will follow, starting from two integers N and R, each one denoting the number of persons to evaluate and the number of relationships spy-person each one has, then, R lines will follow and will contain two integers R1 and R2, meaning that R1 spies R2.

Output

Will consist in T lines, starting from the string “Scenario #i: “ where i is the number of the test case you're analyzing, print the string “spying” if each spy has as a target a civilian, print “spied” otherwise.

Input

3
3 2
0 1
2 1
3 3
0 1
2 1
0 2
4 2
2 3
0 1

Output

Scenario #1: spying
Scenario #2: spied
Scenario #3: spying

Constraints

1 <= N <= 1000

1 <= R <= 10000

Explanation of the second test case:

Spy 0 spies civilian 1, spy 2 spies civilian 1, spy 0 spies spy 2. (Spied case).