#include <bits/stdc++.h>
using namespace std;
int nodes, src, dst;
int dist[2048], q[2048], work[2048];
struct edge {
  int to, rev;
  long long f, cap;
};
vector<edge> g[2048];
void add_edge(int s, int t, long long cap) {
  g[s].push_back((edge){t, ((int)(g[t]).size()), 0, cap});
  g[t].push_back((edge){s, ((int)(g[s]).size()) - 1, 0, 0});
}
bool dinic_bfs() {
  fill(dist, dist + nodes, -1);
  dist[src] = 0;
  int qt = 0;
  q[qt++] = src;
  for (int qh = 0; qh < qt; qh++) {
    int u = q[qh];
    for (int i = 0, ThxDem = ((int)(g[u]).size()); i < ThxDem; ++i) {
      edge& e = g[u][i];
      int v = g[u][i].to;
      if (dist[v] < 0 && e.f < e.cap) dist[v] = dist[u] + 1, q[qt++] = v;
    }
  }
  return dist[dst] >= 0;
}
long long dinic_dfs(int u, long long f) {
  if (u == dst) return f;
  for (int& i = work[u]; i < ((int)(g[u]).size()); i++) {
    edge& e = g[u][i];
    if (e.cap <= e.f) continue;
    int v = e.to;
    if (dist[v] == dist[u] + 1) {
      long long df = dinic_dfs(v, min(f, e.cap - e.f));
      if (df > 0) {
        e.f += df;
        g[v][e.rev].f -= df;
        return df;
      }
    }
  }
  return 0;
}
long long max_flow(int _src, int _dst) {
  src = _src;
  dst = _dst;
  long long r = 0;
  while (dinic_bfs()) {
    fill(work, work + nodes, 0);
    while (long long d = dinic_dfs(src, 1LL << 60)) r += d;
  }
  return r;
}
int n, m, k, c;
int d[605], r[605];
void perdi() {
  printf("0");
  for (int _ = 1, ThxDem = m; _ < ThxDem; ++_) printf(" 0");
  puts("");
}
int main() {
  int tn;
  scanf("%d", &tn);
  while (tn--) {
    scanf("%d%d%d", &n, &m, &k);
    memset(d, 0, sizeof(d));
    for (int i = 0, ThxDem = nodes; i < ThxDem; ++i) g[i].clear();
    nodes = n + m + 2;
    for (int i = 0, ThxDem = m; i < ThxDem; ++i) {
      int x, y;
      scanf("%d%d", &x, &y);
      x--;
      y--;
      d[x]++;
      d[y]++;
      add_edge(2 + x, 2 + n + i, 1);
      add_edge(2 + y, 2 + n + i, 1);
      add_edge(2 + n + i, 1, 1);
    }
    bool can = true;
    int q = 0;
    for (int i = 0, ThxDem = n; i < ThxDem; ++i) {
      int t = d[i];
      if (t > 2 * k) {
        can = false;
        break;
      }
      if (t <= k) continue;
      add_edge(0, 2 + i, (t - k) * 2);
      q += (t - k) * 2;
    }
    if (!can) {
      perdi();
      continue;
    }
    if (max_flow(0, 1) < q) {
      perdi();
      continue;
    }
    memset(r, -1, sizeof(r));
    c = 1;
    for (int i = 0, ThxDem = n; i < ThxDem; ++i) {
      int t = 0;
      for (auto p : g[2 + i]) {
        if (!p.cap) continue;
        if (p.f) {
          int j = p.to - 2 - n;
          r[j] = c;
          t ^= 1;
          if (!t) c++;
        }
      }
    }
    for (int i = 0, ThxDem = m; i < ThxDem; ++i)
      if (r[i] < 0) r[i] = c++;
    for (int i = 0, ThxDem = m; i < ThxDem; ++i)
      printf("%d%c", r[i], " \n"[i == m - 1]);
  }
  return 0;
}
