北极通信网络（Arctic Network）

题目描述

北极某区域共有 \(n\) 座村庄，第 \(i\) 座村庄的坐标为 \((x_i, y_i)\)。 计划为村庄建立通信网络：每座村庄都可配备一部无线电收发机，另有 \(k\) 台卫星设备可分配给任意 \(k\) 个村庄。

• 无线电有一个参数 \(d\)：两村庄间的欧氏距离若不超过 \(d\)，则可直接通过无线电相连。
• 装有卫星设备的两座村庄，无论距离多远，都视为可直接通信（可看作"无限距离直连"）。

目标是在恰当分配 \(k\) 台卫星设备的前提下，通过若干条无线电连接（允许中继），使得所有村庄两两可达，并且所需的无线电参数 \(d\) 尽可能小。请输出这个最小的 \(d\)。

两点 \((x_i, y_i)\) 与 \((x_j, y_j)\) 的欧氏距离定义为 \(\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}\)。

输入格式

• 第一行：两个整数 \(k, n\)（分别表示卫星设备数量与村庄数量）。
• 接下来 \(n\) 行：每行两个整数 \(x_i, y_i\)，表示第 \(i\) 个村庄的坐标。

输出格式

• 输出一行，给出最小的 \(d\)，保留两位小数。

样例

输入

2 4
0 0
0 2
0 4
100 100

输出

2.00

说明 在最优方案中，将 \(k=2\) 台卫星分配给两座相距最远的"簇"的代表村庄，剩余通过无线电连接形成的网络只需 \(d=2.00\)（如在 \(y\) 轴上的三座村庄之间用长度为 \(2\) 的无线电边相连），即可保证全网可达。

约束与提示

• \(1 \le k \le n\)
• 坐标范围可视为 \(|x_i|, |y_i| \le 10^6\)（具体上限以评测为准）