Game#1167
Natasha is preparing the field for a very interesting game. There will be teams participating, and each team must receive one or more trees and a rope. For each team, it should be possible to use the rope to get from any of their assigned trees to any other tree of theirs, without using any trees belonging to other teams. We will consider that the rope allows moving directly between two trees if its length is at least equal to the distance between them.
The length of the rope must be the same for all teams, so that all of them are under equal conditions. Divide all available trees into groups so that the required rope length is as small as possible.
The first line contains two integers and — the number of trees and the number of teams, respectively (1 \leq k \leq n \leq 1000).
Each of the next lines contains two integers x_i and y_i — the coordinates of the -th tree (-10^4 \leq x_i, y_i \leq 10^4).
Print a single real number in the first line — the minimal possible rope length, with at least six digits after the decimal point. In the second line, print numbers from to indicating the team assignments for each tree.
If there are several solutions, print any of them.
Example 1