#include <bits/stdc++.h>
using namespace std;
inline int Read() {
  int x = 0;
  char y;
  bool z = false;
  do y = getchar(), z |= y == '-';
  while (y < '0' || y > '9');
  do x = x * 10 + y - '0', y = getchar();
  while (y >= '0' && y <= '9');
  return z ? -x : x;
}
int fi[605 * 2], c[605 * 2 * 4][3], ss, d[605 * 2];
int n, m, t, p, S = 605 * 2 - 1, T = 605 * 2 - 2, _size;
int ln[605 * 2][2];
inline void Line(int x, int y, int z) {
  c[++ss][0] = y;
  c[ss][1] = fi[x];
  fi[x] = ss;
  c[ss][2] = z;
  c[++ss][0] = x;
  c[ss][1] = fi[y];
  fi[y] = ss;
  c[ss][2] = 0;
  return;
}
int h[605 * 2], li[605 * 2];
int BFS() {
  int le = 1, ri = 1, i;
  memset(h, false, _size);
  h[S] = h[T] = 0;
  h[S] = 1;
  li[1] = S;
  for (; le <= ri; le++)
    for (i = fi[li[le]]; i; i = c[i][1])
      if (c[i][2] && !h[c[i][0]])
        h[c[i][0]] = h[li[le]] + 1, li[++ri] = c[i][0];
  return h[T];
}
int DFS(int x, int y) {
  int i, j = 0, k;
  if (x == T) return y;
  for (i = fi[x]; i && y; i = c[i][1])
    if (c[i][2] && h[c[i][0]] == h[x] + 1) {
      k = DFS(c[i][0], min(y, c[i][2]));
      if (!k) continue;
      y -= k;
      c[i][2] -= k;
      j += k;
      c[i ^ 1][2] += k;
    }
  return j;
}
void Clear() {
  memset(fi, false, _size);
  ss = 1;
  memset(d, false, _size);
  fi[S] = fi[T] = d[S] = d[T] = 0;
  return;
}
int Ans[605 * 2], Now[605 * 2];
bool Check() {
  for (int i = 1; i <= n; i++)
    if ((d[i] - p) * 2 > d[i])
      return false;
    else
      Line(i, T, max((d[i] - p) * 2, 0));
  while (BFS()) DFS(S, 0x7f7f7f7f);
  for (int i = 1; i <= n; i++)
    for (int j = fi[i]; j; j = c[j][1])
      if (c[j][0] == T && c[j][2]) return false;
  return true;
}
int vis[605 * 2];
int main() {
  t = Read();
  while (t--) {
    n = Read();
    m = Read();
    p = Read();
    _size = (n + m + 5) * (sizeof(int));
    Clear();
    for (int i = 1; i <= m; i++) {
      int k = Read(), l = Read();
      ln[i][0] = k;
      ln[i][1] = l;
      Line(S, n + i, 1);
      Line(n + i, k, 1);
      Line(n + i, l, 1);
      d[k]++;
      d[l]++;
    }
    if (!Check()) {
      for (int i = 1; i <= m; i++) Ans[i] = 0;
    } else {
      int ri = 0;
      for (int i = 1; i <= n; i++) Now[i] = 0;
      bool flag = false;
      for (int i = 1; i <= m; i++)
        for (int j = fi[i + n]; j; j = c[j][1]) {
          if (c[j][0] > n) continue;
          if (!c[j][2] || flag) {
            int k = c[j][0];
            if (Now[k])
              Ans[i] = Now[k], Now[k] = 0;
            else
              Ans[i] = Now[k] = ++ri;
            flag = false;
            break;
          }
          flag = true;
        }
    }
    for (int i = 1; i <= m; i++) printf("%d ", Ans[i]);
    puts("");
  }
  return 0;
}
