Domino Chain

A Domino contest is coming to town! Everyone is given a set of dominoes, and the first person to make a chain with all the dominoes win! Each domino has two ends, and two dominoes are connected end to end. Whats the catch? There are two numbers on each domino, and a pair of dominoes can only connect if the connecting ends have the same number!

Being a smart programmer, we’ll write a program to calulate how the dominoes can be connected.

INPUT

There will be multiple test cases. The first line will contain an integer i equal to the number of test cases.
For each test case, the first line will contain an integer n representing the number of dominoes (5 <= n <= 10000). The next n lines will contain descriptions of the dominoes in the following format:

which means the domino has the number a on one end, b on the other end. In this contest, dominoes have numbers from 1 to 100.

OUTPUT

For each test case, output one line. If we cannot build a domino cycle, write "We are doomed for the contest!" Otherwise, output a valid Euler cycle by listing the dominoes in order they are to be linked, each on its on line, with the format

where a in the end linking with the previous domino, b is the end linking with the next domino. The last domino should link back to the first domino. There are often more than one answer, and outputing any correct answer is fine. Output a blank line after each test case.

Sample Input

3
5
1 2
2 3
3 4
4 5
5 6
5
2 1
2 2
3 4
3 1
2 4
4
1 2
2 1
3 4
4 3

Sample Output

We are doomed for the contest!

2 1
1 3
3 4
4 2
2 2

We are doomed for the contest!