#include <bits/stdc++.h>
#define int long long
using namespace std;
int T,n,k,c[2002002],vis[2002002],x[2002002],y[2002002],minv[2002002];
int dis(int a,int b)
{
    return (x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]);
}
void calc(int x,int bl)
{
	for(int j=1;j<=n;j++)
    {
		if(vis[j])
            continue;
		int d=dis(x,j);
		if(d<minv[j])
		{
		    minv[j]=d;
		    c[j]=bl;
        }
	}
}
signed main()
{
    cin>>T;
	for(int ww=1;ww<=T;ww++)
    {
        cin>>n>>k;
		for(int i=1;i<=n;i++)
        {
			minv[i]=1ll<<60;
            c[i]=0;
            vis[i]=0;
            cin>>x[i]>>y[i];
		}
		c[1]=1;
		vis[1]=1;
		int lst=1;
		calc(lst,1);
		for(int i=2;i<=k;i++)
        {
			int nw=0;
			for(int j=1;j<=n;j++)
			{
				if(vis[j])
                    continue;
				if(minv[j]>minv[nw])
                    nw=j;
			}
			c[nw]=i;
			vis[nw]=1;
			lst=nw;
			calc(nw,i);
		}
		for(int i=1;i<=n;i++)
            cout<<c[i]<<' ';
        puts("");
	}
	return 0;
}