저글링 투쟁: 파트 1

이 문제에서 이 문단을 제외한 처음 두 문단은 "Juggle Struggle: Part 2"의 처음 두 문단과 동일하다. 그 외에는 두 문제를 서로 독립적으로 풀 수 있으며, 어느 하나를 읽거나 풀기 위해 다른 하나를 읽거나 풀 필요는 없다.

Graceful Chainsaw Jugglers 그룹의 관리자로서, 당신은 공연을 조금 더 흥미롭게 만들기로 했다. 각 저글러가 각자 자신의 전기톱을 저글링하게 하는 대신, 저글러들이 두 명씩 짝을 이루어 각 쌍이 서로에게 전기톱을 앞뒤로 던지게 하려고 한다. 이 새로운 공연에서는 2 × N명의 저글러가 동시에 무대에 올라 N개의 쌍을 이루며, 각 저글러는 정확히 하나의 쌍에 속한다.

서로 다른 저글러 쌍이 저글링하는 전기톱끼리 충돌할 위험이 있다면 공연이 더 인상적일 것이라고 생각한다. 무대를 이차원 평면이라고 하고, 한 쌍에 속한 두 저글러의 위치를 잇는 그 평면 위의 선분을 그 쌍의 저글링 경로라고 하자. 두 저글링 경로가 교차하면, 그 쌍들이 저글링하는 전기톱은 충돌할 위험이 있다고 한다. 저글러들의 공간상 위치와 짝 구성을 배치라고 한다. 모든 서로 다른 두 저글러 쌍의 전기톱이 충돌할 위험이 있으면 배치는 장엄하다.

많이 고민하고 설계한 끝에 장엄한 배치를 만들어 냈다. 당신은 무대 위 저글러들의 위치와 저글러들의 짝 구성을 종이에 적었다. 불행히도 잘못 던진 전기톱이 종이를 반으로 잘랐고, 짝 구성이 적힌 절반을 잃어버렸다. 무대 장식은 이미 저글러들의 위치를 바탕으로 설계되었으므로 그 위치는 바꿀 수 없다. 큰 기대를 받는 공연의 첫 무대가 불과 몇 시간 앞으로 다가왔으므로, 작동하는 장엄한 배치를 찾아야 한다! 이차원 무대 위 모든 저글러의 위치가 주어질 때, 장엄한 배치를 만드는 짝 구성을 찾아라.

제한

메모리 제한: 1GB. 모든 i에 대해, -$10^{9}$ ≤ $X_{i}$ ≤ $10^{9}$. 모든 i에 대해, -$10^{9}$ ≤ $Y_{i}$ ≤ $10^{9}$. 어느 세 저글러의 위치도 한 직선 위에 있지 않다. (이는 두 저글러가 같은 위치에 있는 일도 없음을 의미한다.) 저글러들의 짝을 지어 그 결과로 얻는 배치를 장엄하게 만드는 방법이 적어도 하나 존재한다.

테스트 세트 1 (공개)

시간 제한: 20초. 1 ≤ T ≤ 100. 2 ≤ N ≤ 100.

테스트 세트 2 (비공개)

시간 제한: 60초. 1 ≤ T ≤ 10. 2 ≤ N ≤ $10^{5}$.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 저글러 쌍의 수인 정수 N 하나가 포함된 한 줄로 시작한다. 그다음 2 × N개의 줄이 주어진다. 이 줄들 중 i번째 줄에는 i번째 저글러의 위치 좌표를 나타내는 두 정수 $X_{i}$와 $Y_{i}$가 주어진다.

각 테스트 케이스마다 모든 i에 대해 저글러 i와 j_{i}를 서로 짝지어야 함을 나타내는 Case #x: j_{1} j_{2} ... j_{2 × N}가 포함된 한 줄을 출력한다. 모든 i에 대해 j_{j_{i}} = i임에 유의하라.

샘플 케이스 #1에서 저글러들의 위치는 정사각형을 이룬다. 유일하게 올바른 해는 저글러 1와 3를 짝짓고, 저글러 2와 4를 짝짓는 것이다.