Spacecraft Malfunction

Interview

Time limit1sMemory limit128 MB

Summary

Given each unit's check reports on two others, exactly one faulty unit, and a faulty unit may lie, find the unique faulty unit or print impossible.

Level: Medium5 of 10
Topics: Brute force, Implementation, Graph, Simulation
Solved: No attempts yet

Problem

It is said that court intrigues began with people lying about others, and then lying about those lies, and so it went. The intriguers were forever looking for a scapegoat, who inevitably turned out to be whoever had the least power — though not always the least morality.

We have run into a similar problem, except this time it is aboard our malfunctioning spacecraft! The spacecraft contains a number of units. The units are so reliable that it would greatly surprise us if more than one were faulty. If more than one were faulty we would lose the probe, so we are certain that exactly one unit is faulty.

Each unit checks exactly two other units, and each unit is checked by at least one other unit. A good unit gives an accurate diagnosis of the units it checks. For example, if unit $X$ is good and it says that $Y$ is faulty and $Z$ is good, then in fact $Y$ is faulty and $Z$ is good. A faulty unit, however, is unreliable: if unit $X$ is faulty and makes the same statements, then $Y$ may or may not be good, and $Z$ may or may not be good either. A unit cannot check itself.

Given the reports from all units, your task is to determine which unit is actually faulty.

Input

The first line contains a single integer $t$ ( $1 \le t \le 10$ ), the number of test cases, followed by the data for each test case.

The first line of each test case contains an integer $n$ ( $3 \le n \le 100$ ), the number of units, followed by $n$ lines, each describing one unit and the results of its checks. Every line starts with a positive integer, the identification number of the unit. After the id number come two pairs of (checked unit id, check result). A check result is a single character, either Y or N, indicating whether the checked unit was reported good or faulty, respectively.

For example, a line 16 8 Y 32 N means that unit $16$ checked unit $8$ and reported it good (Y), and checked unit $32$ and reported it faulty (N).

Output

Print one line per test case. If the faulty unit can be uniquely determined, print its identification number; otherwise — when no candidate is consistent, or more than one is — print the lower-case word impossible.

Examples2

Example 1

Input

1
5
2 16 Y 32 N
16 8 Y 32 N
32 8 N 4 Y
8 4 Y 2 Y
4 2 Y 16 Y

Expected output

Example 2
Input
```
1
3
1 2 N 3 Y
2 1 Y 3 Y
3 2 N 1 Y
```
Expected output
```
2
```