회로 잇기

헥토르는 취업 시장에서의 앞날이 불안해 전자 회로 조립을 배우기로 했다. 가장 먼저 평평한 2차원 기판 위에서 전기 회로를 닫는 일에 도전한다.

기판 한가운데에는 전원선이 지나가고, 그 위에는 왼쪽부터 차례로 $1$번부터 $n$번까지 번호가 매겨진 $n$개의 단자가 놓여 있다. 전원선은 기판을 위쪽 절반과 아래쪽 절반으로 나눈다. 위쪽 절반에는 이미 전선이 깔려 있으며, 다음 규칙을 모두 만족한다.

• 각 전선은 정확히 두 단자를 잇는다.
• 어떤 두 전선도 서로 교차하거나 닿지 않는다.
• 모든 단자는 정확히 하나의 전선에 연결되어 있다.
• 어떤 전선도 전원선을 가로지르지 않는다.

다시 말해 위쪽 전선들은 전원선 위에서 서로 교차하지 않는 호들의 모임, 곧 교차 없는 완전 매칭을 이룬다.

헥토르는 전선을 따라 어떤 단자에서든 다른 모든 단자로 갈 수 있도록 회로를 닫고 싶다. 이를 위해 기판의 아래쪽 절반에 전선을 더 놓으려 한다. 새로 놓는 전선도 위쪽 전선과 똑같은 규칙을 지켜야 한다. 각 전선은 두 단자를 잇고, 새 전선끼리 교차하거나 닿지 않으며, 모든 단자가 정확히 하나의 새 전선에 연결되고, 어떤 새 전선도 전원선을 가로지르지 않는다.

위쪽 전선들이 이미 규칙에 맞는 교차 없는 배치를 이루고 있으므로, 모든 단자가 서로 도달 가능해지도록 아래쪽 전선을 놓는 방법은 항상 존재한다. 그러한 배치를 하나 찾아 출력하라.

첫 줄에 테스트 세트의 개수 $t$가 주어진다 ($1 \le t \le 10$). 이어서 각 테스트 세트가 차례로 주어진다.

각 테스트 세트의 첫 줄에는 짝수 $n$이 주어진다 ($2 \le n \le 10^6$). 전원선 위 단자의 개수다. 다음 $n/2$개의 줄에는 각각 두 정수 $a$, $b$가 주어지며, 위쪽 절반에서 단자 $a$와 $b$가 하나의 전선으로 이어져 있음을 뜻한다.

아래쪽 전선 배치는 여러 가지가 가능하므로, 답을 하나로 정하기 위해 다음과 같이 정의된 표준 배치를 출력한다. 전원선을 순환하는 것으로 보아 $n$번 단자 다음은 $1$번 단자라고 하자. 위쪽 전선이 잇는 두 단자 $a$, $b$에 대해, 바로 다음 단자들을 잇는 아래쪽 전선을 놓는다. 식으로 쓰면 위쪽 전선 $(a, b)$는 아래쪽 전선 $((a \bmod n) + 1,\ (b \bmod n) + 1)$을 만든다.

각 테스트 세트마다 먼저 한 줄에 TAK(폴란드어로 '예')를 출력한다. 이어서 아래쪽 전선 $n/2$개를 출력하되, 각 전선은 두 단자 번호를 작은 쪽부터 한 줄에 적고, 전선들은 첫 번째 단자 번호가 작은 순서대로 나열한다.