Задачи
Игра
Игра
\textit{- Но как он это делает! Он забирается на самую высокую сосну и оттуда планирует.}
\textit{- Ага. Простите, что планирует?}
\textit{"День радио"}
Девочка Наташа готовит поле для очень интересной игры. В ней примут участие \textbf{k} команд, каждая из которых должна получить в своё распоряжение одно или несколько деревьев и верёвку. При этом у каждой команды должна быть возможность с помощью веревки добраться от любого своего дерева до любого другого своего дерева, не используя чужие деревья. Будем считать, что с помощью верёвки можно перебраться с одного дерева на другое напрямую, если её длина не меньше расстояния между ними.
Длина всех верёвок должна быть одинаковой, чтобы поставить все команды в равные условия. Разделите все доступные \textbf{n} деревьев на \textbf{k} наборов так, чтобы необходимая длина верёвок оказалась как можно меньшей.
\InputFile
В первой строке ввода записаны целые числа \textbf{n} и \textbf{k} - количества деревьев и команд, соответственно (\textbf{1} ≤ \textbf{k} ≤ \textbf{n} ≤ \textbf{1000}).
В каждой из следующих \textbf{n} строк записано по два целых числа \textbf{x_i} и \textbf{y_i} - координаты \textbf{i}-го дерева (\textbf{-10^4} ≤ \textbf{x_i}, \textbf{y_i} ≤ \textbf{10^4}).
\OutputFile
В первой строке выведите одно вещественное число не менее, чем с шестью точными знаками после точки - минимально возможную длину верёвки. Во второй выведите \textbf{n} чисел от \textbf{1} до \textbf{k} - номера команд, которым следует присвоить соответствующие деревья.
Если решений несколько, выведите любое.
Входные данные #1
4 2 1 0 0 1 1 1 0 0
Выходные данные #1
1.000000000 1 1 1 2