같은 팀 하자

참가자가 팀원을 직접 고르지 않고 주최 측이 팀을 정해 주는 대회를 연다. 참가자는 저마다 자기를 뺀 나머지 참가자 전원을 같은 팀이 되고 싶은 순서대로 적어서 낸다. 목록의 첫 번째 사람이 가장 같은 팀이 되고 싶은 사람이고, 마지막 사람이 가장 같은 팀이 되기 싫은 사람이다.

참가자 $N$명을 두 명씩 짝지어 모두 팀에 배정한다. 서로 다른 참가자 네 명 A, B, C, D가 있어서 A는 C와 한 팀, B는 D와 한 팀이면서 A는 C보다 B를 더 원하고 B도 D보다 A를 더 원하면, 참가자들은 그 배정을 받아들이지 않는다. 이런 네 명이 없는 배정을 좋은 배정이라고 하자.

좋은 배정은 여러 개일 수 있으므로 그중 하나만 정답으로 받는다. 참가자 $i$의 짝을 $p_i$라고 하면, 좋은 배정 중에서 수열 $p_1, p_2, \dots, p_N$이 사전순으로 가장 앞서는 배정을 구한다. 두 수열은 처음으로 값이 달라지는 자리에서 더 작은 값을 가진 쪽이 사전순으로 앞선다.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫째 줄에는 참가자 수 $N$이 주어진다. 이어지는 $N$개 줄 중 $i$번째 줄에는 참가자 $i$의 선호 목록 $P_{i1}, P_{i2}, \dots, P_{i(N-1)}$이 공백으로 구분되어 주어진다. 이 목록은 $i$를 뺀 나머지 참가자를 $i$가 가장 원하는 사람부터 가장 원하지 않는 사람까지 나열한 것이고, 나머지 참가자 $N-1$명이 정확히 한 번씩 나온다.

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

각 테스트 케이스마다 한 줄씩 출력한다.

좋은 배정이 있으면 사전순으로 가장 앞서는 배정을 팀 목록으로 출력한다. 각 팀은 $i < j$인 두 참가자를 i:j 꼴로 쓰고, 팀은 $i$가 커지는 순서로 정렬해 공백 한 칸으로 구분한다.

좋은 배정이 없으면 NO SOLUTION을 출력한다.