#include <bits/stdc++.h>
using namespace std;
const int N = 200000;
const int INF = 1000000000;
class Dinic {
 private:
  int lt[N], nt[N], bi[N], tl;
  int nw[N], dis[N], vis[N];
  queue<int> Q;

 public:
  int s, e, tot, ci[N];
  int oppo(int t) { return t & 1 ? t + 1 : t - 1; }
  int add_edge(int a, int b, int c) {
    nt[++tl] = lt[a];
    lt[a] = tl;
    bi[tl] = b;
    ci[tl] = c;
    nt[++tl] = lt[b];
    lt[b] = tl;
    bi[tl] = a;
    ci[tl] = 0;
    return tl;
  }
  void flow(int p, int d) {
    ci[p] -= d;
    ci[oppo(p)] += d;
  }
  int dfs(int t, int maxl) {
    int nowl = 0;
    if (t == e) return maxl;
    for (int &p = nw[t]; p; p = nt[p])
      if (dis[t] + 1 == dis[bi[p]] && ci[p]) {
        int d = dfs(bi[p], min(ci[p], maxl - nowl));
        flow(p, d);
        nowl += d;
        if (nowl == maxl) return maxl;
      }
    return nowl;
  }
  void bfs() {
    for (int i = 1; i <= tot; ++i) vis[i] = 0, dis[i] = tot + 1;
    vis[s] = 1;
    dis[s] = 0;
    Q.push(s);
    while (!Q.empty()) {
      int hd = Q.front();
      Q.pop();
      for (int p = lt[hd]; p; p = nt[p])
        if (!vis[bi[p]] && ci[p]) {
          vis[bi[p]] = 1;
          dis[bi[p]] = dis[hd] + 1;
          Q.push(bi[p]);
        }
    }
  }
  int solve() {
    int ans = 0;
    while (1) {
      bfs();
      if (!vis[e]) return ans;
      for (int i = 1; i <= tot; ++i) nw[i] = lt[i];
      ans += dfs(s, INF);
    }
  }
  void init() {
    for (int i = 1; i <= tot; ++i) lt[i] = 0;
    for (int i = 1; i <= tl; ++i) bi[i] = ci[i] = nt[i] = 0;
    s = e = tot = tl = 0;
  }
} F;
int T, n, m, k;
int ai[N], bi[N], av[N], bv[N], cnt[N], now[N], val, tot;
int main() {
  scanf("%d", &T);
  while (T--) {
    F.init();
    scanf("%d%d%d", &n, &m, &k);
    F.s = n + m + 1;
    F.e = F.tot = F.s + 1;
    tot = 0;
    for (int i = 1; i <= n; ++i) cnt[i] = 0;
    for (int i = 1; i <= m; ++i) {
      scanf("%d%d", &ai[i], &bi[i]);
      av[i] = F.add_edge(ai[i], i + n, 1);
      cnt[ai[i]]++;
      bv[i] = F.add_edge(bi[i], i + n, 1);
      cnt[bi[i]]++;
      F.add_edge(i + n, F.e, 1);
    }
    val = 0;
    for (int i = 1; i <= n; ++i)
      if (k < cnt[i])
        F.add_edge(F.s, i, (cnt[i] - k) * 2), val += (cnt[i] - k) * 2;
    if (F.solve() != val) {
      for (int i = 1; i <= m; ++i) printf("%d ", 0);
    } else {
      for (int i = 1; i <= n; ++i) now[i] = 0;
      for (int i = 1; i <= m; ++i)
        if (F.ci[av[i]]) {
          if (!now[ai[i]]) {
            now[ai[i]] = ++tot;
            printf("%d ", now[ai[i]]);
          } else {
            printf("%d ", now[ai[i]]);
            now[ai[i]] = 0;
          }
        } else if (F.ci[bv[i]]) {
          if (!now[bi[i]]) {
            now[bi[i]] = ++tot;
            printf("%d ", now[bi[i]]);
          } else {
            printf("%d ", now[bi[i]]);
            now[bi[i]] = 0;
          }
        } else
          printf("%d ", ++tot);
    }
    puts("");
  }
}
