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