思路：二分枚举建边，用DLX判断是否满足。
#include<set>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<string>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define clr(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define mp make_pair
#define Maxn 20010
#define LL __int64
#define Abs(x) ((x)>0?(x):(-x))
#define lson(x) (x<<1)
#define rson(x) (x<<1|1)
#define inf 100000000
#define lowbit(x) (x&(-x))
#define Mod 1000000007
using namespace std;
int L[Maxn], R[Maxn], U[Maxn], D[Maxn];
int id, ans, S[Maxn], H[Maxn], C[Maxn];
int cnt,n,m;
double dis[][],edge[];
struct Point{
double x,y;
}p[Maxn];
double Dis(Point a,Point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool vis[];
void Link(int r, int c)
{
U[id] = c;
D[id] = D[c];
U[D[c]] = id;
D[c] = id;
if (H[r] < )
H[r] = L[id] = R[id] = id;
else
{
L[id] = H[r];
R[id] = R[H[r]];
L[R[H[r]]] = id;
R[H[r]] = id;
}
S[c]++;
C[id++] = c;
}
void Remove(int c)
{
int i;
for (i = D[c]; i != c; i = D[i])
{
L[R[i]] = L[i];
R[L[i]] = R[i];
}
}
void Resume(int c)
{
int i;
for (i = D[c]; i != c; i = D[i])
L[R[i]] = R[L[i]] = i;
}
int A()
{
int i, j, k, res;
memset(vis, false,sizeof(vis));
for (res = , i = R[]; i; i = R[i])
{
if (!vis[i])
{
res++;
for (j = D[i]; j != i; j = D[j])
{
for (k = R[j]; k != j; k = R[k]){
vis[C[k]] = true;
// cout<<i<<" "<<j<<" "<<k<<" "<<C[k]<<endl;
}
}
}
}
return res;
}
bool dfs (int step) {
if (step + A() > m) return false;
if (R[] == ) return true;
int temp = inf, id;
for (int i = R[]; i ; i = R[i]) {
if (S[i] < temp) {
temp = S[i];
id = i;
}
}
for (int i = D[id]; i != id; i = D[i]) {
Remove(i);
for (int j = R[i]; j != i; j = R[j]) {
Remove(j);
}
if (dfs(step + )) {
return true;
}
for (int j = L[i]; j != i; j = L[j]) {
Resume(j);
}
Resume(i);
}
return false;
}
void Init(int m)
{
int i;
for (i = ; i <= m; i++)
{
R[i] = i + ;
L[i + ] = i;
U[i] = D[i] = i;
S[i] = ;
}
R[m] = ;
id = m + ;
}
void build(int pos)
{
int i,j;
Init(n);
for(i=;i<=n;i++){
H[i]=-;
for(j=;j<=n;j++){
if(dis[i][j]<=edge[pos])
Link(i,j);
}
}
}
void solve()
{
int i,j;
int l,r,mid;
l=,r=cnt;
while(l<r){
mid=(l+r)>>;
build(mid);
if(dfs())
r=mid;
else
l=mid+;
}
printf("%.6lf\n",edge[l]);
}
int main()
{
int i,j,t;
//freopen("ttt.txt","r",stdin);
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
for(i=;i<=n;i++){
scanf("%lf%lf",&p[i].x,&p[i].y);
}
cnt=;
for(i=;i<=n;i++){
for(j=i+;j<=n;j++){
dis[i][j]=dis[j][i]=Dis(p[i],p[j]);
edge[++cnt]=dis[i][j];
}
dis[i][i]=;
}
edge[++cnt]=;
sort(edge+,edge++cnt);
int num=;
for(i=;i<=cnt;i++){
if(edge[i]!=edge[num]){
edge[++num]=edge[i];
}
}
cnt=num;
solve();
}
return ;
}