eolymp
bolt
Try our new interface for solving problems
Problems

Radio Transmitters (RU)

Radio Transmitters (RU)

Time limit 4 seconds
Memory limit 256 MiB

Известно, что если рядом расположены два передатчика, вещающие на одной частоте, то качество приема резко ухудшается. Вам даны местоположения N передатчиков. Известно, что каждый из них может использовать одну из двух доступных частот. Мощности всех передатчиков равны между собой и равны W. В данном случае под мощностью пониматеся радиус действия уверенного приема вокруг передатчика. Какую наибольшую мощность W могут иметь эти передатчики, чтобы не существовало области положительной площади уверенного приема двух передатчиков, вещающих на одинаковой частоте? Выбор частоты вещания каждого передатчика остается за вами. Профессор Кнутмен утверждает, что существует решение этой задачи за время, пропорциональное квадрату числа N, и это решение достаточно эффективно для полного решения этой задачи.

Input data

В первой строке входного файла содержится целое число N (3N7500) - количество передатчиков. Далее в N строках записаны координаты каждого передатчика. Все координаты - целые числа, не превосходящие 10000 по абсолютной величине. Все передатчики имеют различные координаты.

Output data

В первую строку выведите максимальную мощность передатчиков W. Мощность выводите с 7 знаками после запятой. Во вторую строку выведите N чисел - номера частот передатчиков. Число 1 в i-той позиции обозначает, что i-ый передатчик должен вещать на первой частоте. Число 2 обозначает, что на второй. Если решений несколько, выведите любое.

Examples

Input example #1
4
0 0
0 1
1 0
1 1
Output example #1
0.7071068
1 2 2 1
Author М.Левин
Source Зимние сборы в Харькове 2010 День 3