Game
- But how does he do it! He climbs the tallest pine and glides from there.
- Aha. Sorry, what does he plan?
"Radio Day"
Natasha is setting up the field for an exciting game. There will be k teams participating, and each team needs access to one or more trees along with a rope. Each team must be able to reach any of its trees from any other tree within its group using the rope, without relying on trees assigned to other teams. The rope allows direct movement between two trees if its length is at least the distance between them.
All teams must use ropes of the same length to ensure fairness. Your task is to divide the n available trees into k groups such that the length of the rope required is minimized.
Input
The first line of the input provides two integers, n and k, representing the number of trees and teams, respectively (1 ≤ k ≤ n ≤ 1000).
Each of the following n lines contains two integers, x_i and y_i, which are the coordinates of the i-th tree (-10^4 ≤ x_i, y_i ≤ 10^4).
Output
On the first line, output a single real number with at least six decimal places, representing the minimum possible rope length. On the second line, output n numbers ranging from 1 to k, indicating the team numbers to which each tree is assigned.
If there are multiple valid solutions, you may output any one of them.