#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
struct edge {
  int from, to;
  ll f, c;
};
vector<edge> edges;
vector<vector<int>> adjlist, hs;
vector<ll> ec;
vector<int> cur, H;
int addEdge(int from, int to, ll c) {
  int res = (int)(edges).size();
  adjlist[from].push_back((int)edges.size());
  edges.push_back(edge{from, to, 0, c});
  adjlist[to].push_back((int)edges.size());
  edges.push_back(edge{to, from, 0, 0});
  return res;
}
void addFlow(int id, ll f) {
  if (ec[edges[id].to] == 0 && f > 0)
    hs[H[edges[id].to]].push_back(edges[id].to);
  edges[id].f += f;
  edges[id ^ 1].f -= f;
  ec[edges[id].to] += f;
  ec[edges[id].from] -= f;
}
ll maxFlow(int s, int t) {
  int n = adjlist.size();
  hs.assign(2 * n, {});
  ec.assign(n, 0);
  cur.assign(n, 0);
  H.assign(n, 0);
  H[s] = n;
  ec[t] = 1;
  vector<int> co(2 * n);
  co[0] = n - 1;
  for (int id : adjlist[s]) addFlow(id, edges[id].c);
  for (int hi = 0;;) {
    while (hs[hi].empty())
      if (!hi--) return -ec[s];
    int u = hs[hi].back();
    hs[hi].pop_back();
    while (ec[u] > 0) {
      if (cur[u] == adjlist[u].size()) {
        H[u] = 2 * n;
        for (int i = 0; i < adjlist[u].size(); i++) {
          int id = adjlist[u][i];
          if (edges[id].c - edges[id].f > 0 && H[u] > H[edges[id].to] + 1) {
            H[u] = H[edges[id].to] + 1;
            cur[u] = i;
          }
        }
        co[H[u]]++;
        if (!--co[hi] && hi < n) {
          for (int i = 0; i < n; i++) {
            if (hi < H[i] && H[i] < n) {
              co[H[i]]--;
              H[i] = n + 1;
            }
          }
        }
        hi = H[u];
      } else if (edges[adjlist[u][cur[u]]].c - edges[adjlist[u][cur[u]]].f >
                     0 &&
                 H[u] == H[edges[adjlist[u][cur[u]]].to] + 1) {
        addFlow(adjlist[u][cur[u]],
                min(ec[u],
                    edges[adjlist[u][cur[u]]].c - edges[adjlist[u][cur[u]]].f));
      } else {
        cur[u]++;
      }
    }
  }
}
bool hasFlow(int id) { return edges[id].f != 0; }
struct redge {
  int from, to;
  int label;
  int mF, mT, kF, kT;
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int t;
  cin >> t;
  for (int _ = 0; _ < t; ++_) {
    edges.clear();
    int n, m, k;
    cin >> n >> m >> k;
    adjlist = vector<vector<int>>(2 * n + m + 2);
    vector<vector<int>> adj(n);
    vector<redge> redges;
    for (int i = 0; i < m; ++i) {
      int a, b;
      cin >> a >> b;
      --a;
      --b;
      adj[a].push_back(i);
      adj[b].push_back(i);
      addEdge(0, i + 1, 1);
      int mF = addEdge(i + 1, m + a + 1, 1);
      int mT = addEdge(i + 1, m + b + 1, 1);
      int kF = addEdge(i + 1, m + n + a + 1, 1);
      int kT = addEdge(i + 1, m + n + b + 1, 1);
      redges.push_back(redge{a, b, i, mF, mT, kF, kT});
    }
    bool broken = false;
    int sum = 0;
    for (int i = 0; i < n; ++i) {
      if ((int)(adj[i]).size() > 2 * k) {
        broken = true;
        break;
      }
      int need = max(0, (int)(adj[i]).size() - k);
      addEdge(m + i + 1, m + 2 * n + 1, max(0, need));
      addEdge(m + n + i + 1, m + 2 * n + 1, max(0, need));
      sum += 2 * need;
    }
    if (broken) {
      for (int i = 0; i < m; ++i) cout << "0 ";
      cout << '\n';
      continue;
    }
    int flow = (int)maxFlow(0, m + 2 * n + 1);
    if (flow != sum) {
      for (int i = 0; i < m; ++i) cout << "0 ";
      cout << '\n';
      continue;
    }
    vector<vector<int>> keep(n), change(n);
    for (int i = 0; i < m; ++i) {
      if (hasFlow(redges[i].mF)) keep[redges[i].from].push_back(i);
      if (hasFlow(redges[i].mT)) keep[redges[i].to].push_back(i);
      if (hasFlow(redges[i].kF)) change[redges[i].from].push_back(i);
      if (hasFlow(redges[i].kT)) change[redges[i].to].push_back(i);
    }
    for (int i = 0; i < n; ++i) {
      int u = (int)(change[i]).size();
      for (int j = 0; j < u; ++j) {
        redges[change[i][j]].label = redges[keep[i][j]].label;
      }
    }
    for (int i = 0; i < m; ++i) cout << redges[i].label + 1 << " ";
    cout << "\n";
  }
}
