Power plants

In the far future humanity moved to a large, warm planet covered in vegetation, and it is building power plants on a huge scale to supply the new colony. The plants draw on the vast energy of the universe. The builders missed one fact: two power plants built too close together carry a serious risk of a chain reaction, and a chain reaction ends in a large explosion.

A plant can run on one of two kinds of energy, light and dark, and the two kinds do not react with each other. If some plants run on light energy and the rest on dark energy, plants of the same kind can be kept farther apart, which makes the whole project safer.

You are given the positions of $n$ power plants. The planet is large enough that the plants are treated as points in the plane. Assign light energy or dark energy to every plant so that the smallest Euclidean distance between two plants of the same kind is as large as possible. Since $n \ge 3$, some pair of plants always shares a kind, so that smallest distance always exists.

The first line contains one integer $N$ ($3 \le N \le 10^5$), the number of power plants.

The $i$-th of the next $N$ lines contains two integers $x_i$ and $y_i$ ($0 \le x_i, y_i \le 10^9$), the coordinates of plant $i$. All points are distinct.

Print the square of the largest distance that can be achieved on the first line. The square is printed instead of the distance itself so that the answer avoids real numbers. The coordinates are integers, so this value is always an integer.

Print the number of plants running on light energy on the second line, and their numbers in increasing order, separated by single spaces, on the third line. Print the plants running on dark energy on the fourth and fifth lines in the same format.

Several assignments can reach the optimum, so print only the lexicographically smallest one. Write an assignment as a sequence $c_1, c_2, \dots, c_N$ of length $N$, where $c_i = 0$ if plant $i$ runs on light energy and $c_i = 1$ if it runs on dark energy. Print the assignment whose sequence is lexicographically smallest. Under this rule plant 1 always runs on light energy.