Join My Team

You are running a contest where the organizers assign the teams instead of letting the participants pick their own. Every participant hands in a list of all the other participants, ordered by how much they want that person as a teammate. The first name on the list is the person they want most, the last name is the person they want least.

Assign all $N$ participants to teams of exactly two. The participants reject an assignment when there are four different participants A, B, C, D such that A is on a team with C, B is on a team with D, A wants B more than C, and B wants A more than D. An assignment with no such four participants is called good.

Several good assignments can exist, so only one of them counts as the answer. Let $p_i$ be the partner of participant $i$. Among all good assignments, report the one whose sequence $p_1, p_2, \dots, p_N$ is lexicographically smallest. One sequence is lexicographically smaller than another when it holds the smaller value at the first position where the two sequences differ.

The first line holds the number of test cases $T$.

Each test case starts with a line holding the number of participants $N$. Line $i$ of the following $N$ lines holds the preference list of participant $i$, given as $P_{i1}, P_{i2}, \dots, P_{i(N-1)}$ separated by spaces. The list names every participant other than $i$, ordered from the one participant $i$ wants most to the one participant $i$ wants least, and each of the other $N-1$ participants appears exactly once.

• $1 \le T \le 20$
• $2 \le N \le 100$
• $1 \le P_{ij} \le N$
• $P_{ij} \ne i$

Print one line for each test case.

If a good assignment exists, print the lexicographically smallest one as a list of teams. Write each team as i:j with $i < j$, sort the teams by increasing $i$, and separate them with single spaces.

If no good assignment exists, print NO SOLUTION.