저글 스트러글: Part 1

이 문제의 처음 두 문단(이 문단 제외)과 'Juggle Struggle: Part 2'의 처음 두 문단은 같습니다. 두 문제는 서로 독립적으로 풀 수 있으므로, 하나를 읽거나 풀기 위해 다른 문제를 먼저 읽거나 풀 필요는 없습니다.

Graceful Chainsaw Jugglers 단체의 매니저로서 공연을 조금 더 화려하게 만들기로 했습니다. 저글러가 각자 혼자서 전기톱을 던지는 대신, 두 명이 짝을 이루어 서로 전기톱을 주고받게 하려 합니다. 이번 공연에는 동시에 $2 \times N$명의 저글러가 무대에 오르며, 이들은 정확히 한 쌍에 속하는 $N$개의 쌍으로 나뉩니다.

서로 다른 쌍이 던지는 전기톱은 두 쌍의 경로가 교차하면 충돌할 위험이 있습니다. 무대는 2차원 평면입니다. 한 쌍의 두 저글러를 잇는 선분을 그 쌍의 저글링 경로라고 합니다. 두 저글링 경로가 교차하면 두 쌍의 전기톱은 충돌할 위험이 있습니다. 저글러들의 위치와 짝짓기를 합쳐 배치라고 합니다. 모든 두 쌍의 전기톱이 충돌할 위험이 있으면 그 배치는 훌륭하다고 합니다.

훌륭한 배치를 찾아 저글러들의 위치와 짝짓기를 종이에 적어 두었습니다. 그런데 나쁜 전기톱 투구로 종이가 반으로 찢어져, 짝짓기가 적힌 절반을 잃어버렸습니다. 무대 장식은 이미 저글러들의 위치를 기준으로 설계되어 있어 위치는 바꿀 수 없습니다. 공연 데뷔까지 몇 시간밖에 남지 않았습니다. 2차원 무대 위 모든 저글러의 위치가 주어질 때, 훌륭한 배치를 만드는 짝짓기를 찾으세요.

첫 줄에는 테스트 케이스의 개수 $T$가 주어집니다. 이어서 $T$개의 테스트 케이스가 나옵니다. 각 테스트 케이스는 쌍의 개수 $N$이 적힌 한 줄로 시작합니다. 그 뒤로 $2 \times N$줄이 주어지며, $i$번째 줄에는 $i$번 저글러의 좌표를 나타내는 정수 $X_i$와 $Y_i$가 있습니다.

각 테스트 케이스마다 Case #x: j1 j2 ... j2×N 형식으로 한 줄을 출력합니다. 이는 모든 $i$에 대해 저글러 $i$와 저글러 $j_i$가 짝이 된다는 뜻입니다. 모든 $i$에 대해 $j_{j_i} = i$가 성립합니다.

• 모든 $i$에 대해 $-10^9 \le X_i \le 10^9$입니다.
• 모든 $i$에 대해 $-10^9 \le Y_i \le 10^9$입니다.
• 세 저글러의 위치가 한 직선 위에 놓이는 경우는 없습니다. 같은 위치에 있는 두 저글러도 없습니다.
• 훌륭한 배치를 만드는 짝짓기가 적어도 하나 존재합니다.

예제 1에서 저글러들의 위치는 정사각형을 이룹니다. 유효한 해는 1번과 3번을 짝짓고, 2번과 4번을 짝짓는 것 하나뿐입니다.