RPLD - Database


Gaby enjoy working in a database of a very important university, this university has students of course, each student can see as many subjects they want, however, the database suffered an attack by a group of hackers, now, Gaby needs to see the backup files, but then she noticed that some of the backup files are corrupted as well... For example, the backup file can show that a student is seeing 2 same subjects, desperate, she needs help on this task.

It is known that several students (different ones) can see the same subject, however, one single student cannot see the same subject (this would seem ridiculous), if one student sees the same subject two or more times, this test would belong to a corrupted file.

Input

First line will contain an integer T, representing the cases to evaluate, the next T cases will start with a N and R, both integers, denoting the number of students and the number of lines the database have, the next R lines contains two integers I and C, I stands for the ID of the students and C for the subject code.

Output

You will output T lines for each test case, starting with the string “Scenario #i: “ where i is the test case you're evaluating, then, you should output the string “impossible” if the database file on evaluation is corrupted and the string “possible” if its not.

Example

INPUT:
2
2 4
1 6102
1 6103
2 6102
2 6103

2 4
1 6102
1 6102
2 6102
2 6103

Output:
Scenario #1: possible
Scenario #2: impossible

Constraints

1 <= N <= 10000
1 <= R <= 100000
1 <= I <= N
1000 <= C <= 9999


hide comments
vengatesh15: 2017-02-16 14:26:35

used vector and AC in 1 go.

shubiks: 2016-07-10 00:21:02

Used STL map<int,set>
AC in one go! :D

partha2717: 2016-05-26 11:56:33

Am getting wrong answer is i can't understand are there space included in the output printing syntax?
If anyone can check my submission please. (16994732)

Narendra pal: 2015-08-08 23:08:36

used stl and pairs...AC in 1 go ;)

kartikay singh: 2015-08-08 22:05:44

@SWAPNIL
keep going :P

swapnil1996: 2015-08-08 22:04:22

STL all the way....!!! :)

[Mayank Pratap]: 2015-08-08 17:51:11

Good for beginners like me to learn STL..:)

Anmol Varshney: 2015-07-18 21:42:41

STL Pair FTW

Vamsi Krishna Avula: 2015-04-02 15:43:46

In Python, reading the whole data and converting to ints itself took me 0.35s.
Best solution took 0.04s. How is this even possible?
Are input files modified?

(Francky) => I think there's no trouble here, my old PY-2.7-code still got AC in 0.04s.

re(vamsi): Thanks for the reply! I see those conversions are unnecessary. 0.12 0.11 0.10 0.07s now.

Last edit: 2015-04-04 12:31:10
Asheesh Pathak: 2015-03-31 18:46:10

Nothing more than inbuilt STLs.


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