Гра
- Але як він це робить! Він забирається на найвищу сосну і звідти планиє.
- Ага. Пробачте, що планує?
"День радіо"
Дівчмнка Наташа готує поле для дуже цікавої гри. У ній приймуть участь 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 - номери команд, яким потрібно присвоїти відповідні дерева.
Якщо розв'язків декілька, виведіть довільний.