발전소

먼 미래에 인류는 넓고 따뜻하며 초목이 무성한 행성으로 이주했고, 새 식민지에 전력을 대려고 발전소를 대규모로 짓고 있다. 발전소는 우주의 막대한 에너지를 그대로 끌어다 쓴다. 그런데 건설진이 놓친 사실이 하나 있다. 발전소 두 개를 너무 가깝게 지으면 연쇄 반응이 일어날 위험이 크고, 연쇄 반응의 끝은 대형 폭발이다.

발전소가 쓸 수 있는 에너지는 빛 에너지와 어둠 에너지 두 가지이고, 이 둘은 서로 반응하지 않는다. 일부 발전소를 빛 에너지로, 나머지를 어둠 에너지로 돌리면 같은 종류끼리 거리를 더 벌릴 수 있어 공사 전체가 그만큼 안전해진다.

발전소 $n$개의 위치가 주어진다. 행성이 충분히 넓으므로 발전소는 평면 위의 점으로 본다. 모든 발전소에 빛 에너지나 어둠 에너지를 배정해서, 같은 종류의 에너지를 쓰는 두 발전소 사이의 유클리드 거리 중 최솟값을 최대로 만들어라. $n \ge 3$이므로 같은 종류를 쓰는 발전소 쌍은 항상 존재하고, 따라서 이 최솟값도 항상 존재한다.

첫째 줄에 발전소의 개수 $N$이 주어진다 ($3 \le N \le 10^5$).

다음 $N$개 줄 중 $i$번째 줄에 $i$번 발전소의 좌표 $x_i$, $y_i$가 주어진다 ($0 \le x_i, y_i \le 10^9$). 모든 점은 서로 다르다.

첫째 줄에 얻을 수 있는 최대 거리의 제곱을 출력한다. 실수를 출력하지 않으려고 거리 자체가 아니라 제곱을 출력한다. 좌표가 정수이므로 이 값은 항상 정수이다.

둘째 줄에 빛 에너지를 쓰는 발전소의 개수를, 셋째 줄에 그 발전소의 번호를 오름차순으로 공백 하나씩 띄어 출력한다. 넷째 줄과 다섯째 줄에는 어둠 에너지를 쓰는 발전소를 같은 형식으로 출력한다.

최적인 배정이 여러 가지면 그중 사전순으로 가장 작은 하나만 출력한다. 배정을 길이 $N$인 수열 $c_1, c_2, \dots, c_N$으로 적고, $i$번 발전소가 빛 에너지를 쓰면 $c_i = 0$, 어둠 에너지를 쓰면 $c_i = 1$이라 하자. 이 수열이 사전순으로 가장 작아지는 배정을 출력하면 된다. 이 규칙을 따르면 1번 발전소는 항상 빛 에너지를 쓴다.