#include<bits/stdc++.h>
using namespace std;
const int N=1919810;
typedef long long ll;
typedef pair<ll,ll> PII;
ll n,m,k;
ll a[N],b[N];
char s[N];
bool tf[N];
int res[N];


void __(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        res[i]=m;
    }
    for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);
    vector<PII> v;
    v.push_back({a[1],b[1]});
    res[1]=1;

    for(int i=2;i<m;i++){
        ll dist=1e19,t=0;
        for(int j=1;j<=n;j++){
            if(res[j]!=m) continue;
            ll mn=0;
            for(auto [x,y]:v){
                ll res=(x-a[j])*(x-a[j])+(y-b[j])*(y-b[j]);
                mn=max(mn,res);
            }
            if(mn<=dist){
                dist=mn;
                t=j;
            }
        }
        v.push_back({a[t],b[t]});
        res[t]=i;
    }
    // cout<<n<<" "<<m<<endl;
    for(int i=1;i<=n;i++) printf("%d ",res[i]);
    printf("\n");
}

int main(){
    int _;
    cin>>_;
    while(_--){
        __();
    }
}