题目描述

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

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

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

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

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

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

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

输入格式

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

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

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

输出格式

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

数据范围

$1≤S≤100, S≤P≤500,0≤x,y≤10000$

样例

1
2 4
0 100
0 300
0 600
150 750

212.13

来源

• POJ2349
• 算法竞赛进阶指南