#include <bits/stdc++.h>
using namespace std;
const int N = 610;
const int maxN = N + N, maxE = (N + 2 * N + N) * 2;
const long long oo = 1e18;
long long src, snk, cap[maxE];
int head[maxN], headcpy[maxN], nxt[maxE], to[maxE], edgeCnt;
void init() {
  memset(head, -1, sizeof head);
  edgeCnt = 0;
}
void addedge(int u, int v, long long c) {
  nxt[edgeCnt] = head[u];
  head[u] = edgeCnt;
  cap[edgeCnt] = c;
  to[edgeCnt++] = v;
}
void addbiedge(int u, int v, long long c) {
  addedge(u, v, c);
  addedge(v, u, 0);
}
int Rank[maxN];
long long ddfs(int cur = src, long long flow = oo) {
  if (cur == snk) return flow;
  for (int &i = headcpy[cur]; i != -1; i = nxt[i]) {
    int t = to[i];
    if (!cap[i] || Rank[t] != Rank[cur] + 1) continue;
    long long f = ddfs(t, min(flow, cap[i]));
    cap[i] -= f;
    cap[i ^ 1] += f;
    if (f) return f;
  }
  return 0;
}
int Q[maxN];
bool dbfs() {
  memset(Rank, -1, sizeof Rank);
  int Qi = 0;
  Q[Qi++] = src;
  Rank[src] = 0;
  for (int i = 0; i < Qi; ++i) {
    int cur = Q[i];
    int r = Rank[cur];
    for (int j = head[cur]; j != -1; j = nxt[j]) {
      int t = to[j];
      if (!cap[j] || Rank[t] != -1) continue;
      Rank[t] = r + 1;
      Q[Qi++] = t;
      if (t == snk) return 1;
    }
  }
  return 0;
}
long long dinic() {
  long long ret = 0, f;
  while (dbfs()) {
    memcpy(headcpy, head, sizeof head);
    while (f = ddfs()) {
      ret += f;
    }
  }
  return ret;
}
int t, n, m, k, u[N], v[N], req[N];
vector<int> helpEdges[N];
void pr() {
  for (int i = 0; i < m; ++i) printf("0%c", " \n"[i + 1 == m]);
}
int main() {
  scanf("%d", &t);
  while (t--) {
    scanf("%d", &n), scanf("%d", &m), scanf("%d", &k);
    init();
    for (int i = 0; i < n; ++i) req[i] = 0;
    for (int i = 0; i < m; ++i) {
      scanf("%d", &u[i]);
      scanf("%d", &v[i]);
      u[i]--, v[i]--;
      req[u[i]]++;
      req[v[i]]++;
    }
    bool can = 1;
    for (int i = 0; i < n; ++i) {
      if (req[i] > 2 * k)
        can = 0;
      else if (req[i] > k && req[i] <= 2 * k)
        req[i] = 2 * (req[i] - k);
      else
        req[i] = 0;
    }
    if (!can) {
      pr();
      continue;
    }
    src = n + m;
    snk = src + 1;
    for (int i = 0; i < m; ++i) {
      addbiedge(src, i, 1);
      addbiedge(i, m + u[i], 1);
      addbiedge(i, m + v[i], 1);
    }
    int sumreq = 0;
    for (int i = 0; i < n; ++i) {
      addbiedge(m + i, snk, req[i]);
      sumreq += req[i];
    }
    int flow = dinic();
    if (flow != sumreq) {
      pr();
      continue;
    }
    for (int cur = 0; cur < m; cur++) {
      for (int j = head[cur]; j != -1; j = nxt[j]) {
        if (to[j] != src && cap[j] == 0) helpEdges[to[j] - m].push_back(cur);
      }
    }
    int id = 1;
    vector<int> col(m, 0);
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j + 1 < helpEdges[i].size(); j += 2) {
        col[helpEdges[i][j]] = id;
        col[helpEdges[i][j + 1]] = id++;
      }
    }
    for (int i = 0; i < m; ++i)
      if (!col[i]) col[i] = id++;
    for (int i = 0; i < m; ++i) printf("%d%c", col[i], " \n"[i + 1 == m]);
    for (int i = 0; i < n; ++i) helpEdges[i].clear();
  }
}
