#include <bits/stdc++.h>
using namespace std;

class DSU {
	vector<int> a;
public:
	DSU(int n) : a(n) {
		iota(a.begin(), a.end(), 0);
	}
	int query(int x) {
		if (a[x] != x)
			a[x] = query(a[x]);
		return a[x];
	}
	void merge(int x, int y) {
		a[query(x)] = query(y);
	}
};

using llf = long double;

struct P {
	int64_t x, y;
};

llf dis(P a, P b) {
	int64_t dx = a.x - b.x;
	int64_t dy = a.y - b.y;
	return sqrt(llf(dx * dx + dy * dy));
}

pair<int, int> closest(const vector<P> &a) {
	struct cmp_y {
		bool operator()(const pair<P, int> &p, const pair<P, int> &q) const {
			return tie(p.first.y, p.second) < tie(q.first.y, q.second);
		}
	};
	set<pair<P, int>, cmp_y> s;

	pair<int, int> ans = {0, 1};
	vector<int> o(a.size());
	iota(o.begin(), o.end(), 0);
	sort(o.begin(), o.end(), [&](int p, int q) {
		return tie(a[p].x, a[p].y) < tie(a[q].x, a[q].y);
	});
	llf d = 1e100; int pt = 0;
	for (int i = 0; i < int(a.size()); ++i) {
		while (pt < i and a[o[i]].x - a[o[pt]].x >= d) {
			s.erase({a[o[pt]], o[pt]});
			pt += 1;
		}
		auto it = s.lower_bound({P(a[o[i]].x, a[o[i]].y - d), -1});
		while (it != s.end() and it->first.y - a[o[i]].y < d) {
			llf curd = dis(it->first, a[o[i]]);
			if (curd < d) {
				ans = {it->second, o[i]};
				d = curd;
			}
			it++;
		}
		s.emplace(a[o[i]], o[i]);
	}
	return ans;
}


int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int t;
	cin >> t;
	while (t--) {
		int n, k;
		cin >> n >> k;
		vector<P> a(n);
		for (auto &[x, y] : a)
			cin >> x >> y;
		DSU dsu(n);
		unordered_set<int> s;
		for (int i = 0; i < k; ++i)
			s.insert(i);
		for (int i = k; i < n; ++i) {
			vector<int> v;
			vector<P> que;
			s.insert(i);
			for (auto si : s) {
				v.push_back(si);
				que.push_back(a[si]);
			}
			auto [x, y] = closest(que);
			dsu.merge(v[x], v[y]);
			s.erase(v[x]);
			s.erase(v[y]);
			s.insert(v[x]);
		}
		vector<int> ans(n);
		for (int i = 0; i < n; ++i)
			if (dsu.query(i) == i)
				ans[i] = k--;
		for (int i = 0; i < n; ++i)
			cout << ans[dsu.query(i)] << " \n"[i + 1 == n];
	}
	return 0;
}