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