Problem I
Tree Validator

A tree made to Kermit’s specification

redAttention: This problem is HARD! Only attempt to solve it after you are done with the other problems.

Kermit the Parrot wants a tree to perch on. He has $N$ favorite spots, and would like them to be connected by this tree. Kermit is very particular about his tree, so he wants it to be created according to his specifications.

Kermit gave Coriander, the gardening cat, $N-1$ subsets ($E_1, E_2, \ldots , E_{N-1}$) of the set $V = \{ 1, 2, \ldots , N\} $. Coriander’s tree is to connect two elements of each set, in such a way that the resulting tree is completely connected.

More formally, Coriander should choose a pair of elements $(a_ i, b_ i)$ from each set $E_ i$ such that the graph formed by all these edges is connected.

Coriander reported a list of $N - 1$ pairs $(a, b)$ she claims would build a tree to Kermit’s satisfaction, or she claimed the problem is unsolvable. You are asked to verify her claim.

Input

The first line of input contains a single integer $N$ ($1 \le N \le 10^5$), the size of the set $V$.

The next $N-1$ lines contain the description of each of the sets $E_ i$. The $i-th$ of these lines starts with an integer $s_ i$ ($2 \le s_ i \le N$) indicating the size of $E_ i$, followed by $s_ i$ integers in strictly increasing order (each one in $V$). The sum of all $s_ i$ is not larger than $2 \cdot 10^5$.

The next line contains Coriander’s assessment of Kermit’s problem. This can be either “YES” or “NO”.

In case Coriander’s says “YES”, $N-1$ lines follow, each one with two distinct integers $a$ and $b$ ($1 \le a, b \le N$) representing an edge of their output. Note that these edges might be given in any order.

Output

The output should contain a single line, which can be either:

• WHO IS A GOOD KITTY?

• CORIANDER FOUND A SOLUTION BUT THERE ARE NONE

• CORIANDER FOUND NO SOLUTIONS BUT THERE ARE SOME

• CORIANDER’S OUTPUT IS NOT ONE OF THE CORRECT TREES

5
2 1 2
3 1 2 3
3 3 4 5
2 4 5
NO

CORIANDER FOUND NO SOLUTIONS BUT THERE ARE SOME

5
2 1 2
3 1 2 3
3 3 4 5
2 4 5
YES
4 5
3 4
1 3
1 2

WHO IS A GOOD KITTY?

5
2 1 2
3 1 2 3
4 1 3 4 5
2 4 5
YES
1 2
2 3
1 3
4 5

CORIANDER'S OUTPUT IS NOT ONE OF THE CORRECT TREES

3
2 1 2
2 1 2
YES
1 2
2 3

CORIANDER FOUND A SOLUTION BUT THERE ARE NONE

3
2 1 2
2 1 2
NO

WHO IS A GOOD KITTY?