题目描述

北极的某区域共有n座村庄( 1 ≤ n ≤ 500 )，每座村庄的坐标用一对整数(x, y)表示，其中 0 ≤ x, y ≤ 10000。为了加强联系，决定在村庄之间建立通讯网络。通讯工具可以是无线电收发机，也可以是卫星设备。所有的村庄都可以拥有一部无线电收发机， 且所有的无线电收发机型号相同。但卫星设备数量有限，只能给一部分村庄配备卫星设备。  不同型号的无线电收发机有一个不同的参数d，两座村庄之间的距离如果不超过d就可以用该型号的无线电收发机直接通讯，d值越大的型号价格越贵。拥有卫星设备的两座村庄无论相距多远都可以直接通讯。

现在有k台卫星设备，请你编写程序计算出如何分配可以使所拥有的无线电收发机的d值最小，并保证任意两个村庄都可以直接或间接通讯

输入格式

 The first line of input contains N, the number of test cases. The first line of each test case contains 1 <= S <= 100, the number of satellite channels, and S < P <= 500, the number of outposts. P lines follow, giving the (x,y) coordinates of each outpost in km (coordinates are integers between 0 and 10,000).

第一行输入包含N，即测试数据的数量。 每个测试用例的第一行包含1 <= S <= 100，卫星数，S <P <= 500，即前哨数。 P行，给出每个前哨（km，坐标是0到10,000之间的整数）的（x，y）坐标。

输出格式

 每个样例输出一个最小d值，两位小数

样例

1
2 4
0 100
0 300
0 600
150 750

212.13

提示

对于所有测试点，1<=N<=10。

来源：鸣谢thewalker88上传