#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
//#define int long long
using pii = pair<int, int>;
using ll = long long;
auto dis2 = [&](pii a, pii b)->int {
return abs(a.first - b.first) + abs(a.second - b.second);
};
pair<int, int> closest(const vector<pii>& a) {
int64_t d = dis2(a[0], a[1]);
pair<int, int> ans = { 0, 1 };
for (int i = 0; i < int(a.size()); ++i) {
for (int j = i + 1; j < int(a.size()); ++j) {
pii cur = { i,j };
int64_t curd = dis2(a[i], a[j]);
if (curd < d) {
ans = cur;
d = curd;
}
}
}
return ans;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tt = 1;
cin >> tt;
while (tt--) {
int n, k;
cin >> n >> k;
vector<int>x(n + 1), y(n + 1);
for (int i = 1; i <= n; i++) {
cin >> x[i] >> y[i];
}
set<int>s;
for (int i = 1; i <= k; i++) {
s.insert(i);
}
//
vector<int>p(n + 1);
for (int i = 1; i <= n; i++) {
p[i] = i;
}
auto find = [&](auto find, int x)->int {
if (p[x] != x)return p[x] = find(find, p[x]);
return p[x];
};
for (int i = k + 1; i <= n; i++) {
vector<int> v;
vector<pii> que;
s.insert(i);
for (auto si : s) {
v.push_back(si);
que.push_back({x[si],y[si]});
}
pii it=closest(que);
int x = it.first, y = it.second;
int ai = find(find, v[x]), bi = find(find, v[y]);
p[ai] = bi;
s.erase(v[x]);
s.erase(v[y]);
s.insert(v[x]);
}//return 0;
vector<int>c(n + 1);
for (int i = 1; i <= n; i++) {
if (find(find, i) == i) {
c[i] = k--;
}
}
for (int i = 1; i <= n; i++) {
cout << c[find(find, i)] << ' ';
}
cout << endl;
}
}