패턴 잠금 | cho.sh

문제

안드로이드 휴대폰은 비밀번호 대신 패턴 잠금을 자주 사용한다. 잠금 화면에는 점 아홉 개가 3 x 3 격자로 놓여 있으며, 왼쪽 위 모서리부터 오른쪽 아래 모서리까지 1부터 9까지 번호가 매겨져 있다.

1 2 3
4 5 6
7 8 9

패턴은 점들을 원하는 순서로 이어 하나의 연속된 선으로 그린다. 올바른 패턴은 다음을 만족해야 한다.

점을 4개 이상 사용한다.
하나로 이어진 선을 이룬다(여러 조각으로 끊겨서는 안 된다).
각 점을 최대 한 번만 지난다.

예를 들어 순서 2-1-5-3-6-8-4-7-9는 올바른 패턴이다.

점을 건너뛰는 것에 관한 규칙이 하나 더 있다. 두 점을 잇는 직선이 다른 한 점을 지난다면, 그 가운데 점을 이미 지난 경우에만 두 점을 곧바로 이을 수 있다. 가운데 점을 아직 지나지 않았다면 두 점을 곧바로 이을 수 없는데, 선이 그 가운데 점을 반드시 지나게 되기 때문이다. 패턴 2-1-5-3-6-8-4-7-9에서 7에서 9로 가는 단계는 8을 지나간다. 8을 이미 앞에서 지났으므로 이 이동은 허용된다. 만약 8을 지나지 않았다면 7에서 9로 곧바로 갈 수 없다.

철수는 자신의 패턴을 잊어버렸지만, 화면에 남은 자국으로 그가 그린 모양을 알 수 있고, 이를 기하 그래프로 나타낸다. 이 그래프의 간선은 단위 선분이다. 각 간선은 같은 행, 같은 열, 또는 대각선에서 사이에 다른 점이 없이 바로 이웃한 두 점을 잇는다. 어떤 이동이 이미 지난 가운데 점을 건너뛰면, 그 가운데 점 양옆의 단위 선분 두 개가 자국으로 남는다(예를 들어 8을 지나 7에서 9로 가면 선분 7-8과 8-9가 남는다). 따라서 그래프에는 점을 건너뛰는 긴 선분이 절대 들어 있지 않으며, 그런 이동은 항상 두 개의 절반 선분으로 나타난다.

이러한 기하 그래프가 주어질 때, 정확히 그 그래프를 그릴 수 있는 패턴을 복원하라. 모든 그래프가 복원되는 것은 아니다. 끊어진 그래프는 하나의 선에서 나올 수 없고, 이어져 있어도 어떤 올바른 패턴으로도 만들 수 없는 그래프가 있다. 어떤 그래프는 오직 하나의 패턴으로만, 또 어떤 그래프는 여러 패턴으로 만들 수 있다.

입력

입력은 표준 입력으로 주어지며 $T$ 개의 테스트 케이스로 이루어진다. 첫 줄에 정수 $T$ 가 주어진다.

각 테스트 케이스의 첫 줄에는 기하 그래프의 간선 수를 나타내는 정수 $e$ ( $3 \le e \le 24$ )가 주어진다. 이어지는 $e$ 개의 줄에는 각각 두 정수 $s_i$ 와 $d_i$ ( $1 \le s_i, d_i \le 9$ )가 주어지며, 이는 점 $s_i$ 와 점 $d_i$ 를 잇는 간선을 뜻한다.

출력

표준 출력으로 답을 쓴다. 각 테스트 케이스에 대해, 주어진 그래프를 정확히 그리는 올바른 패턴이 있으면 그 패턴을 점 번호로 나타내어 한 칸(공백)으로 구분해 출력한다. 그런 패턴이 없으면 IMPOSSIBLE을 출력한다.

같은 그래프를 그리는 올바른 패턴이 여러 개라면, 사전순으로 가장 작은 것을 출력한다. 두 패턴을 앞에서부터 한 자리씩 비교했을 때, 처음으로 달라지는 자리의 점 번호가 더 작은 쪽이 더 작은 패턴이다. 한 그래프의 모든 올바른 패턴은 그래프에 나오는 점들을 정확히 모두 지나므로 길이가 서로 같다.