题目描述

国防部（DND）希望通过无线网络连接几个北部前哨站。

在建立网络时将使用两种不同的通信技术：每个前哨站都有一个无线电收发器，一些前哨站还有一个通信卫星。

任意两个拥有通信卫星的前哨站不论它们的位置如何，都可以通过卫星进行通信。

而如果利用无线电进行通信，则需要两个前哨站的距离不能超过 $D$ 方可进行通信。

而 $D$ 的大小取决于收发器的功率，收发器的功率越大，$D$ 也就越大，但是需要的成本也就越高。

出于采购和维护的考虑，所有的前哨站都采用相同的收发器，也就是说所有前哨站的无线电通信距离 $D$ 都是相同的。

你需要确定在保证任意两个前哨站之间都能进行通信（直接或间接）的情况下，$D$ 的最小值是多少。

输入格式

第一行包含整数 $N$，表示共有 $N$ 组测试数据。

每组数据的第一行包含两个整数 $S$ 和 $P$，其中 $S$ 为卫星个数，$P$ 为前哨站个数。

接下来 $P$ 行每行包含两个整数 $x$ 和 $y$，分别表示一个前哨站的横纵坐标。

输出格式

输出一个实数，表示 $D$ 的最小值，结果保留两位小数。

样例

输入样例：

1
2 4
0 100
0 300
0 600
150 750

输出样例：

212.13

样例解释

有 $S=2$ 个卫星，$P=4$ 个前哨站。

坐标：

• A: (0,100)
• B: (0,300)
• C: (0,600)
• D: (150,750)

距离： AB = 200, AC = 500, AD ≈ 761.58, BC = 300, BD ≈ 474.34, CD ≈ 212.13。

卫星可以让两个站无视距离直接通信。
我们可以将卫星分配给距离最远的两个站，然后用无线电连接其他站。

实际上，这是求最小生成树中第 $S$ 大的边的长度（因为 $S$ 个卫星可以替代 $S-1$ 条最长的边）。
按距离从小到大加边，当连通块数等于 $S$ 时，当前边的长度就是 $D$ 的最小值。

在这个例子中，最小生成树的三条边从小到大排序是 200, 212.13, 300。
有 $S=2$ 个卫星，可以替代最长的一条边（300），所以最大需要的无线电距离是 212.13。

数据范围

• $1 \le S \le 100$
• $S \le P \le 500$
• $0 \le x, y \le 10000$

时空限制

• 时间限制：1 秒
• 空间限制：64 MB