저글링 고군분투: 파트 2

이 문제와 "Juggle Struggle: Part 1"의 처음 두 문단(이 문단은 제외)은 동일하다. 그 밖의 부분에서는 두 문제를 서로 독립적으로 풀 수 있으며, 한 문제를 읽거나 풀기 위해 다른 문제를 읽거나 풀 필요는 없다.

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

서로 다른 저글러 쌍이 저글링하는 전기톱끼리 충돌할 위험이 있다면 공연이 더 인상적일 것이라고 생각한다. 무대를 이차원 평면이라고 하고, 한 쌍에 속한 두 저글러의 위치를 잇는 이 평면 위의 선분을 그 쌍의 저글링 경로라고 하자. 두 저글링 경로가 교차하면, 해당 쌍들이 저글링하는 전기톱이 충돌할 위험이 있다고 한다. 저글러들의 공간적 위치와 짝 구성을 배치라고 한다. 모든 두 저글러 쌍의 전기톱이 충돌할 위험이 있으면 그 배치는 훌륭하다. 즉, 배치가 훌륭하려면 N개의 저글링 경로 선분 각각이 나머지 N-1개의 저글링 경로 선분 각각과 교차해야 한다(단, 이 교차점들이 반드시 모두 같은 위치에 있어야 하는 것은 아니다).

막바지 수정을 몇 차례 거친 뒤, 당신은 훌륭하다고 생각되는 배치를 완성했다. 서둘러 구성한 만큼, 이 배치가 실제로 훌륭한지 판정할 수 있는 검사기를 작성하려고 한다. 훌륭하지 않다면, 다른 모든 쌍과 교차하지 못하는 저글러 쌍은 최대 25개이다. 검사기가 점검을 위해 그러한 저글러 쌍을 모두 나열해 주기를 원한다.

제한

메모리 제한: 1GB. -$10^{9}$ ≤ $X_{i}$ ≤ $10^{9}$, 모든 i에 대해. -$10^{9}$ ≤ $Y_{i}$ ≤ $10^{9}$, 모든 i에 대해. -$10^{9}$ ≤ X'{i} ≤ $10^{9}$, 모든 i에 대해. -$10^{9}$ ≤ Y'{i} ≤ $10^{9}$, 모든 i에 대해. 어떤 세 저글러의 위치도 한 직선 위에 있지 않다. (이는 두 저글러가 같은 위치에 있는 경우도 없음을 뜻한다.) 최대 25개의 저글러 쌍을 제외한 모든 저글러 쌍에 대해, 그 저글링 경로는 다른 N - 1개의 모든 저글링 경로와 교차한다. 참고: 저글러들을 짝지어 그 결과로 얻은 배치를 훌륭하게 만드는 방법이 존재할 수도 있고 존재하지 않을 수도 있다.

테스트 세트 1 (공개)

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

테스트 세트 2 (비공개)

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

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 저글러 쌍의 수를 나타내는 하나의 정수 N이 담긴 한 줄로 시작한다. 그다음 N개의 줄이 주어진다. 이 중 i번째 줄에는 네 정수 $X_{i}$, $Y_{i}$, X'{i}, Y'{i}가 주어진다. ($X_{i}$, $Y_{i}$)와 (X'{i}, Y'{i})는 i번째 저글러 쌍을 구성하는 두 저글러 위치의 좌표이다.

각 테스트 케이스마다 Case #x: y을 담은 한 줄을 출력한다. 입력이 훌륭한 배치를 나타내면 y는 대문자 MAGNIFICENT이다. 그렇지 않으면 y는 정수로 이루어진 엄격히 증가하는 목록이어야 한다. 정수 i는 i번째 저글러 쌍의 저글링 경로가 적어도 하나의 다른 저글링 경로와 교차하지 못할 때, 그리고 그럴 때에만 이 목록에 있어야 한다.

예제 케이스 #1에는 쌍이 두 개뿐이며, 그 경로들은 교차하지 않는다.

예제 케이스 #2의 배치는 훌륭하다. 모든 쌍의 경로가 다른 모든 쌍의 경로와 교차한다.

예제 케이스 #3에서는 3번 쌍의 경로만 다른 모든 쌍의 경로와 교차한다.