농장 울타리 설계

큰 농장을 사서 울타리를 두르려고 한다. 농장에는 이미 울타리 기둥 $N$개가 박혀 있고, 변호사들은 기둥을 하나도 남기지 말고 전부 쓰라고 못을 박았다.

기둥은 평면 위의 점이다. 울타리는 기둥 $N$개의 순서 하나다. 첫 번째 기둥과 두 번째 기둥, 두 번째와 세 번째를 차례로 직선으로 잇고, 마지막 기둥은 첫 번째 기둥과 잇는다. 이렇게 만든 도형은 자기 자신과 닿지 않는 다각형이어야 한다. 기둥마다 울타리 선분이 정확히 두 개 모이고, 기둥이 아닌 점에는 선분이 둘 이상 지나가지 않는다.

농장은 넓게 남겨야 한다. 기둥 몇 개를 빼도 된다면 둘러쌀 수 있는 최대 면적을 $A$라고 하자. 이 값은 기둥들의 볼록 껍질 면적과 같다. 만들 울타리는 $A / 2$보다 넓은 면적을 둘러싸야 한다.

첫 줄에 테스트 케이스 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 기둥 수 $N$이 주어진다. 기둥에는 $0$번부터 $N - 1$번까지 번호가 붙어 있다. 이어지는 $N$개 줄에는 $i$번 기둥의 좌표 $X_i$와 $Y_i$가 정수로 주어진다.

• 기둥 $N$개의 위치는 모두 다르고, 전부 한 직선 위에 있지는 않다.
• $1 \le T \le 30$
• $3 \le N \le 1000$
• $-50000 \le X_i, Y_i \le 50000$

각 테스트 케이스마다 한 줄에 "Case #x: "를 출력하고, 이어서 $0$부터 $N - 1$까지 서로 다른 정수 $N$개를 공백 하나로 구분해 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, 정수들은 울타리를 세우는 순서대로 나열한 기둥 번호다. 마지막 기둥은 첫 기둥과 이어진다.

조건을 만족하는 순서는 여러 가지이므로, 출력할 순서는 다음 방법으로 정한다.

기둥을 $X$ 오름차순으로 정렬하고, $X$가 같으면 $Y$ 오름차순으로 정렬한다. 이 순서를 기둥 순서라고 부른다. 기둥 순서의 첫 기둥을 $L$, 마지막 기둥을 $R$이라고 하면 둘 다 볼록 껍질의 꼭짓점이다. 볼록 껍질의 경계를 반시계 방향으로 따라갈 때 $L$에서 $R$까지 가는 부분이 아래 사슬이고, $R$에서 $L$까지 가는 부분을 거꾸로 읽은 것이 위 사슬이다. 꼭짓점은 아니면서 볼록 껍질의 변 위에 놓인 기둥은 그 변이 속한 사슬에 들어가고, $L$과 $R$은 두 사슬에 모두 들어간다.

이제 울타리 두 개를 만든다.

• 울타리 U: $L$에서 시작해 위 사슬을 따라 $R$까지 가고, 그다음에 위 사슬에 없는 기둥을 모두 기둥 순서의 역순으로 잇는다.
• 울타리 D: $L$에서 시작해 아래 사슬을 따라 $R$까지 가고, 그다음에 아래 사슬에 없는 기둥을 모두 기둥 순서의 역순으로 잇는다.

두 울타리는 모두 자기 자신과 닿지 않고, 둘 중 면적이 더 넓은 쪽은 항상 $A / 2$보다 넓다. 그 울타리를 위에서 설명한 순서대로 $L$부터 출력한다. 두 울타리의 면적이 같으면 울타리 U를 출력한다.

울타리가 둘러싸는 면적은 $A$를 넘지 못한다. 어떤 울타리든 기둥들의 볼록 껍질 안에 머물기 때문이다.

두 울타리의 면적이 같은 경우도 흔하다. 모든 기둥이 볼록 껍질의 경계에 있는 입력에서는 두 울타리 모두 볼록 껍질 자체를 그린다. $N = 3$이면 어떤 순서를 골라도 같은 삼각형이 된다.