#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3f;
struct dinic {
  const bool scaling = false;
  int lim;
  struct edge {
    int to, cap, rev, flow;
    bool res;
    edge(int to_, int cap_, int rev_, bool res_)
        : to(to_), cap(cap_), rev(rev_), flow(0), res(res_) {}
  };
  vector<vector<edge>> g;
  vector<int> lev, beg;
  dinic(int n) : g(n) {}
  void add(int a, int b, int c) {
    g[a].push_back(edge(b, c, g[b].size(), false));
    g[b].push_back(edge(a, 0, g[a].size() - 1, true));
  }
  bool bfs(int second, int t) {
    lev = vector<int>(g.size(), -1);
    lev[second] = 0;
    beg = vector<int>(g.size(), 0);
    queue<int> q;
    q.push(second);
    while (q.size()) {
      int u = q.front();
      q.pop();
      for (auto& i : g[u]) {
        if (lev[i.to] != -1 or (i.flow == i.cap)) continue;
        if (scaling and i.cap - i.flow < lim) continue;
        lev[i.to] = lev[u] + 1;
        q.push(i.to);
      }
    }
    return lev[t] != -1;
  }
  int dfs(int v, int second, int first = INF) {
    if (!first or v == second) return first;
    for (int& i = beg[v]; i < g[v].size(); i++) {
      auto& e = g[v][i];
      if (lev[e.to] != lev[v] + 1) continue;
      int foi = dfs(e.to, second, min(first, e.cap - e.flow));
      if (!foi) continue;
      e.flow += foi, g[e.to][e.rev].flow -= foi;
      return foi;
    }
    return 0;
  }
  long long max_flow(int second, int t) {
    long long first = 0;
    for (lim = scaling ? (1 << 30) : 1; lim; lim /= 2)
      while (bfs(second, t))
        while (int ff = dfs(second, t)) first += ff;
    return first;
  }
  vector<pair<int, int>> get_cut(int second, int t) {
    max_flow(second, t);
    vector<pair<int, int>> cut;
    vector<int> vis(g.size(), 0), st = {second};
    vis[second] = 1;
    while (st.size()) {
      int u = st.back();
      st.pop_back();
      for (auto e : g[u])
        if (!vis[e.to] and e.flow < e.cap) vis[e.to] = 1, st.push_back(e.to);
    }
    for (int i = 0; i < g.size(); i++)
      for (auto e : g[i])
        if (vis[i] and !vis[e.to] and !e.res) cut.push_back({i, e.to});
    return cut;
  }
};
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n, m, k;
    cin >> n >> m >> k;
    map<pair<int, int>, int> mp;
    vector<pair<int, int>> eg;
    vector<int> dg(n);
    int pt = 0;
    vector<vector<int>> g(n);
    for (int i = 0; i < m; i++) {
      int a, b;
      cin >> a >> b;
      a--, b--;
      if (a > b) swap(a, b);
      pair<int, int> p = {a, b};
      eg.push_back(p), mp[p] = pt++;
      dg[a]++, dg[b]++;
      g[a].push_back(b), g[b].push_back(a);
    }
    int second = n + m, st = n + m + 1;
    dinic D(n + m + 2);
    bool has = true;
    for (int i = 0; i < n; i++) {
      if (dg[i] <= k) continue;
      if (dg[i] > 2 * k) {
        has = false;
        break;
      }
      D.add(second, i, 2 * (dg[i] - k));
      for (auto u : g[i]) {
        pair<int, int> p = {i, u};
        if (i > u) p = {u, i};
        D.add(i, n + mp[p], 1);
      }
    }
    for (auto p : eg) D.add(mp[p] + n, st, 1);
    D.max_flow(second, st);
    for (auto e : D.g[second]) {
      if (e.flow < e.cap) has = false;
    }
    if (!has) {
      for (int i = 0; i < m; i++) cout << 0 << " ";
      cout << '\n';
      continue;
    }
    int color = 1;
    vector<int> ans(m);
    for (int i = 0; i < n; i++)
      if (dg[i] > k) {
        vector<int> v;
        for (auto e : D.g[i])
          if (e.cap == e.flow) v.push_back(e.to - n);
        for (int j = 0; j < int(v.size()); j += 2) {
          ans[v[j]] = ans[v[j + 1]] = color++;
        }
      }
    for (int i = 0; i < m; i++)
      if (!ans[i]) ans[i] = color++;
    for (auto u : ans) cout << u << " ";
    cout << '\n';
  }
  exit(0);
}
