Problem C: 再续网络

Problem C: 再续网络

Time Limit: 2 Sec  Memory Limit: 128 MB
Submit: 155  Solved: 52
[Submit] [Status] [Web Board] [Creator:]

Description

国防部希望通过无线网络连接几个北部前哨站。在建立网络时将使用两种不同的通信技术:每个前哨站都有一个无线电收发器,一些前哨站还有一个卫星信道。
任何带卫星频道的两个前哨站都可以通过卫星进行通信,无论其位置如何。否则,两个前哨只有当它们之间的距离不超过D时才可以通过无线电进行通信,这取决于收发器的功率。更高的功率产生更高的D但成本更高。由于采购和维护考虑,前哨的收发器必须相同;也就是说,每对前哨的D值都是相同的。
您的工作是确定收发器所需的最小D。使每对前哨之间必须至少有一条通信路径(直接或间接)。

Input

第一行输入包含N,即测试用例的数量。每个测试用例的第一行包含S,P(1 <= S <= 100)S为卫星数量,P为卫星信道的数量,并且S <P <= 500。 接下来P行,为每个哨岗的(x,y)坐标,单位为km(坐标为0到10,000之间的整数)

Output

对于每种情况,输出为整连接网络所需的最小数。(保留两位小数)

Sample Input Copy

1
2 4
0 100
0 300
0 600
150 750

Sample Output Copy

212.13