RPLE - Espionage

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).


Added by:david_8k
Date:2012-04-12
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem used for the RPL contest

hide comments
2013-01-31 18:03:57 guy fawkes
getting wa!! no idea where the bug is!! any hints???
2012-07-29 06:31:16 Shubham Somani
running loop in O(n)...yet getting TLE in python...plz help
2012-07-14 15:38:25 V Sriharsha
Persons numbered from 0 to n-1?
2012-05-31 00:44:48 Matt Renaud
I'm getting SIGABRT when I submit and I have no clue why :S Could someone take a look, ID: 7064931

Thanks
2012-04-18 11:17:59 RAJDEEP GUPTA
@Alex Anderson: I think this is mostly because of fast input method.Since the first few users of this problem are always solving problems in much less time.
2012-04-17 17:53:26 Alex Anderson
@Rajdeep
You can probably use some sort of hash.
It can also be that they just read the input in much faster? If there is a huge amount of it.

Last edit: 2012-04-18 20:49:35
2012-04-16 07:15:07 RAJDEEP GUPTA
how are people solving this in 0.02 or 0.03 secs? My solution is O(max(N,R)). It took 0.18. Any hint??
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.