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

#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
template <typename ...T>
void debug_(const char *s, T ...a) {
    cerr << "\e[1;32m(" << s << ") = (";
    int cnt = sizeof...(T);
    (..., (cerr << a << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename I>
void orange_(const char *s, I L, I R) {
    cerr << "\e[1;32m[ " << s << " ] = [ ";
    for (int f = 0; L != R; ++L)
        cerr << (f++ ? ", " : "") << *L;
    cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

#define IM imag
#define RE real

constexpr int64_t C = 1e9;
// constexpr int maxn = 2000000 + 5;

using i128 = __int128_t;
using lld = int64_t;
using P = complex<int64_t>;

lld norm(P a) {
    return 1LL*RE(a)*RE(a) + 1LL*IM(a)*IM(a);
}

int sgn(lld x) { return (x > 0) - (x < 0); }
lld cross(P a, P b) {
    return 1LL * RE(a) * IM(b) - 1LL * IM(a) * RE(b);
    // lld s = IM(conj(a) * b);
    // return s;
}
int ori(P a, P b, P c) {
    int s = sgn(cross(b - a, c - a));
    return s;
}

#define L(i) ((i)==0 ? 2 : (i)-1)
#define R(i) ((i)==2 ? 0 : (i)+1)
#define FOR for (int i = 0; i < 3; i++)
bool in_cc(const array<P, 3> &p, P q) {
    i128 det = 0;
    FOR det += i128(norm(p[i]) - norm(q)) * cross(p[R(i)] - q, p[L(i)] - q);
    return det > 0;
}
struct Tri;
struct E {
    Tri *t;
    int side;
    E() : t(0), side(0) {}
    E(Tri *t_, int side_) : t(t_), side(side_) {}
};
struct Tri {
    array<P, 3> p;
    array<Tri *,3> ch;
    array<E, 3> e;
    Tri() {}
    Tri(P a, P b, P c) : p{a, b, c}, ch{} {}
    bool has_chd() const { return ch[0] != nullptr; }
    bool contains(P q) const { 
        FOR if (ori(p[i], p[R(i)], q) < 0) return false;
        return true;
    }
} *pool/*pool[maxn * 10]*/, *it;
void link(E a, E b) {
    if (a.t) a.t->e[a.side] = b;
    if (b.t) b.t->e[b.side] = a;
}
struct Trigs {
    Tri *root;
    Trigs() {
        root = new(it++) Tri(P(-C, -C), P(C*2, -C), P(-C, C*2));
    }
    void add_point(P p) {
        add_point(find(p, root), p);
    }
    static Tri *find(P p, Tri *r) {
        while (r->has_chd()) for (Tri *c: r->ch)
            if (c && c->contains(p)) { r = c; break; }
        return r;
    }
    void add_point(Tri *r, P p) {
        array<Tri *, 3> t;
        FOR t[i] = new(it++) Tri(r->p[i], r->p[R(i)], p);
        FOR link(E(t[i], 0), E(t[R(i)], 1));
        FOR link(E(t[i], 2), r->e[L(i)]);
        r->ch = t;
        FOR flip(t[i], 2);
    }
    void flip(Tri *A, int a) {
        auto [B, b] = A->e[a];
        if (!B || !in_cc(A->p, B->p[b])) return;
        Tri *X = new(it++)Tri(A->p[R(a)],B->p[b],A->p[a]);
        Tri *Y = new(it++)Tri(B->p[R(b)],A->p[a],B->p[b]);
        link(E(X,0), E(Y,0));
        link(E(X,1), A->e[L(a)]); link(E(X,2), B->e[R(b)]);
        link(E(Y,1), B->e[L(b)]); link(E(Y,2), A->e[R(a)]);
        A->ch = B->ch = {X, Y, nullptr};
        flip(X, 1); flip(X, 2); flip(Y, 1); flip(Y, 2);
    }
};
vector<Tri *> res;
set<Tri *> vis;
void go(Tri *now) {
    if (!vis.insert(now).second) return;
    if (!now->has_chd()) return res.push_back(now);
    for (Tri *c: now->ch) if (c) go(c);
}
void build(vector<P> &ps) {
    it = pool;
    res.clear();
    vis.clear();
    shuffle(ps.begin(), ps.end(), mt19937(114514));
    Trigs tr; for (P p: ps) tr.add_point(p);
    go(tr.root);
}


vector<P> convex_hull(vector<P> v) {
    sort(all(v), [](P &a, P & b) {
        return make_pair(RE(a), IM(a)) < make_pair(RE(b), IM(b));
    });

    if (v[0] == v.back()) return {v[0]};
    int t = 0, s = 1; vector<P> h(v.size() + 1);
    for (int _ = 2; _--; s = t--, reverse(all(v)))
        for (P p: v) {
            while (t > s && ori(p, h[t-1], h[t-2]) >= 0) t--;
            h[t++] = p;
        }
    return h.resize(t), h;
}

lld farthest(vector<P> &p) {
    int n = p.size(), pos = 1;
    lld ans = 0;
    for (int i = 0; i < n; i++) {
        P e = p[(i + 1) % n] - p[i];
        while (cross(e, p[(pos + 1) % n] - p[i]) > cross(e, p[pos] - p[i]))
            pos = (pos + 1) % n;
        for (int j: {i, (i + 1) % n})
            ans = max(ans, norm(p[pos] - p[j]));
    }
    return ans;
}

struct Dsu {
    vector<int> pa;
    int anc(int x) {
        return pa[x]==x ? x : pa[x]=anc(pa[x]);
    }
    bool join(int x, int y) {
        x = anc(x), y = anc(y);
        if (x == y) return false;
        pa[y] = x;
        return true;
    }
    Dsu(int n) : pa(n) {
        iota(all(pa), 0);
    }
};



int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        pool = new Tri[n * 8];

        vector<P> p(n);
        map<pair<int,int>, int> mp;
        for (int i = 0; i < n; i++) {
            int x, y;
            cin >> x >> y;
            mp[{x, y}] = i;
            p[i] = {x, y};
        }

        build(p);

        const auto gid = [&mp](P &q) {
            if (RE(q) >= C || RE(q) <= -C || IM(q) >= C || IM(q) <= -C) return -1;
            if (auto jt = mp.find({RE(q), IM(q)}); jt != mp.end())
                return jt->second;
            return -1;
        };

        vector<tuple<lld,int,int>> e, te;
        for (auto *pp: res) {
            for (int x = 0; x < 3; x++) {
                auto p1 = pp->p[x], p2 = pp->p[(x + 1) % 3];

                int i = gid(p1);
                int j = gid(p2);
                if (i != -1 && j != -1) {
                    lld d = norm(p1 - p2);
                    e.emplace_back(d, i, j);
                }
            }
        }

        sort(all(e));
        Dsu dsu(n);

        int CC = n;
        for (auto &[w, i, j]: e) {
            if (CC == k) {
                te.emplace_back(w, i, j);
                continue;
            }

            if (dsu.join(i, j)) {
                --CC;
            }

        }


        vector<int> id(n);
        int ctr = 0;
        for (int i = 0; i < n; i++) {
            if (dsu.anc(i) == i)
                id[i] = ctr++;
        }
        for (int i = 0; i < n; i++) {
            if (dsu.anc(i) != i)
                id[i] = id[dsu.anc(i)];
        }

        for (int i = 0; i < n; i++)
            cout << id[i]+1 << (i+1==n ?
                     '\n' : ' ');

        delete[] pool;
    }
    return 0;
}