RPLA - Answer the boss!

no tags 

Eloy is a hard worker man, however, he is constantly bullied by his superiors, molested by this, one day he was wondering in what “rank” you are, so you can bully the people with lower ranks, also to discover who can really bully Eloy!.

Now, given the number of employees and the number of relations between them, Eloy need you to output the “rank” which employee is in, being 1 the “boss” (not bullied by anybody) and the employee who are in these ranks

Input

There will be an integer T denoting the number of test cases, then, T test cases will follow. Each test case starts with two integers N and R, the number of employees and the number of relations between them. The next R lines consists of two integers R1 and R2, meaning that “employee R1 is lower than employee R2's rank”.

Output

You will output for each test case the string “Scenario #i:” where i is the test case you are analyzing, after that, you will print N lines, for each line you will output the rank of the employee and the employee itself, if there is the same rank for several employees, then output them lexicographically ordered (the first is the lower.)

Sample

Input:
2

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

Output:
Scenario #1:
1 0
2 4
3 2
4 1
4 3
Scenario #2:
1 0
2 1
2 2
3 3
3 4

Blank line between test cases for clarification and separation. Please note that can be more than one "boss" (not bullied by anybody.)

Constraints

1 <= N <= 1000; 1 <= R <= 10000


hide comments
krish: 2015-04-04 08:21:00

@adjimmy
Scenario #1:
1 0
1 1
2 2
2 3
2 6
3 4
3 5

Ankur Mohanty: 2015-01-22 18:11:19

be careful about the output format

Akhilesh Anandh: 2015-01-05 04:51:43

cout << TLE
printf - accepted

shakaal: 2014-12-22 00:00:44

weak test cases cost 10wa for not including a case

Sudharsansai: 2014-12-15 19:03:30

That completes my Nelson (111)...
BTW , a very Nice question...

californiagurl: 2014-12-05 16:57:58

and today i thank cin/cout for being such giant assholes and giving me TLE and a sleepless night -_-
FINALLY!!!!!
AC
100th

Last edit: 2014-12-06 09:21:22
bony2023: 2014-07-13 15:29:50

Nice one ! :D

Last edit: 2014-07-13 15:30:40
|RAMSDEN|: 2014-07-03 09:32:08

Really a nice problem
enjoyed solving it
AC in first attempt :)

adijimmy: 2014-04-04 12:48:04

what is the output for the test case ?? help me out :(
1
6 5
2 1
3 1
6 1
4 3
5 3

Dhruv Agarwal: 2014-02-13 20:00:13

nice problem

Last edit: 2014-02-13 20:05:40

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