| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 256 MB | 30 | 8 | 7 | 26.923% |
You are putting together a competition similar to IDI Open where the major difference is team selection. The participants are asked to order the other participants according to whom they would like the most to be on their team. The first person on their list is the person they would like the most to be on their team, and the last person is the one they would like the least to be on their team.
Your task is to assign all competitors into teams of two, in such a way that they are happy with the assignment. They are happy with any assignment unless there exists four competitors, A, B, C and D, where A is on C’s team, B is on D’s team, A prefers B to C, and B prefers A to D.
The first line of the input consists of a single integer, T, the number of test cases. Each of the following T cases begins with a line with a single integer, N, the number of participants.
The next N lines each have N − 1 integers, Pij, giving the preference list of participant number i, separated by spaces.
For each test case, output one possible solution that the participants are happy with, given by a list of teams on the form i:j (i is on a team with j), where each team is separated by a space. There may be many such lists, but any of them will be accepted. If there is no solution, output NO SOLUTION.
3 4 2 3 4 3 1 4 1 2 4 1 2 3 8 2 5 4 6 7 8 3 3 6 1 7 8 5 4 4 7 2 8 5 6 1 1 8 3 5 6 7 2 6 1 8 2 3 4 7 7 2 5 3 4 1 8 8 3 6 4 1 2 5 5 4 7 1 2 3 6 6 4 6 2 5 3 6 3 5 1 4 4 5 1 6 2 2 6 5 1 3 4 2 3 6 1 5 1 4 2 3
NO SOLUTION 1:4 2:3 5:6 7:8 1:6 2:3 4:5
Contest > IDI Open Contest > IDI Open 2014 J번