Database

mediumhashmap

Gaby enjoys working in the database of a very important university. This university has students, of course, and each student can be enrolled in as many subjects as they want.

However, the database suffered an attack by a group of hackers. Now, Gaby needs to analyze the backup files. But then she noticed that some of the backup files are corrupted.

For example, the backup file can show that a student is enrolled in the same subject multiple times. Desperate, she needs help with this task.

It is known that several students (different ones) can be enrolled in the same subject. However, a single student cannot be enrolled in the same subject more than once — that would be ridiculous!

If a student appears as being enrolled in the same subject two or more times, then that record belongs to a corrupted file.

Input Format:

The first line contains an integer $$$T$$$ $$$(1 \leq T \leq 900)$$$ — the number of test cases.

Each test case starts with a line containing two integers $$$N$$$ and $$$R$$$ $$$(1 \leq N \leq 10^5,\ 1 \leq R \leq 10^6)$$$ — the number of students and the number of records in the database.

The next $$$R$$$ lines each contain two integers $$$I$$$ and $$$C$$$ $$$(1 \leq I \leq N,\ 1000 \leq C \leq 9999)$$$ — where $$$I$$$ is the student ID and $$$C$$$ is the subject code.

Output Format:

For each test case, print a single line starting with the string Scenario #i: where $$$i$$$ is the test case number (starting from $$$1$$$).

Then, print the string impossible if the database file in that test case is corrupted, or possible if it is not.

Examples:

Example 1:

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

Example 2:

Input:

3
10 10
8 1004
4 1003
1 1002
5 1003
4 1004
1 1000
3 1002
8 1003
8 1004
1 1002
10 10
4 1004
10 1002
1 1003
10 1003
7 1000
8 1001
3 1002
1 1003
10 1004
10 1001
10 10
8 1002
4 1001
6 1000
9 1001
5 1002
2 1003
9 1004
9 1000
5 1001
1 1003

Output:

Scenario #1: impossible
Scenario #2: impossible
Scenario #3: possible

Code

Loading Editor...