#include <bits/stdc++.h>
using namespace std;
struct edge {
  int des;
  int next;
  int w;
  int type;
} e[2 * 100005];
queue<int> q;
int n;
int m;
int k;
int s;
int t;
int u;
int v;
int w;
int cnt;
int head[10005];
int depth[10005];
int cur[10005];
int ans[10005];
void ins(int u, int v, int w) {
  e[++cnt].next = head[u];
  e[cnt].des = v;
  e[cnt].w = w;
  e[cnt].type = 1;
  head[u] = cnt;
  e[++cnt].next = head[v];
  e[cnt].des = u;
  e[cnt].w = 0;
  e[cnt].type = 0;
  head[v] = cnt;
}
int dfs(int u, int flow) {
  if (u == t) return flow;
  for (int i = cur[u]; i != -1; i = e[i].next) {
    cur[u] = e[i].next;
    int v = e[i].des;
    if (depth[v] == depth[u] + 1 && e[i].w > 0) {
      int di = dfs(v, min(flow, e[i].w));
      if (di > 0) {
        e[i].w -= di;
        e[i ^ 1].w += di;
        return di;
      }
    }
  }
  return 0;
}
bool bfs() {
  memset(depth, 0, sizeof(depth));
  depth[s] = 1;
  q.push(s);
  while (!q.empty()) {
    u = q.front();
    q.pop();
    for (int i = head[u]; i != -1; i = e[i].next) {
      v = e[i].des;
      if (depth[v] == 0 && e[i].w > 0) {
        depth[v] = depth[u] + 1;
        q.push(v);
      }
    }
  }
  if (depth[t]) return true;
  return false;
}
int cas;
int rd[10005];
int sum;
void init() {
  cnt = -1;
  sum = 0;
  for (int i = s; i <= t; ++i) head[i] = -1;
  for (int i = 1; i <= n; ++i) rd[i] = 0;
  for (int i = 1; i <= m; ++i) ans[i] = 0;
}
bool add_edge() {
  for (int i = 1; i <= n; ++i) {
    if (rd[i] > k) {
      if (2 * (rd[i] - k) > rd[i]) return false;
      ins(s, i, 2 * (rd[i] - k));
      sum += 2 * (rd[i] - k);
    }
  }
  return true;
}
int main() {
  scanf("%d", &cas);
  while (cas--) {
    scanf("%d %d %d", &n, &m, &k);
    s = 0;
    t = n + m + 1;
    init();
    for (int i = 1; i <= m; ++i) {
      int u;
      int v;
      scanf("%d %d", &u, &v);
      ins(u, i + n, 1);
      ins(v, i + n, 1);
      ins(i + n, t, 1);
      ++rd[u];
      ++rd[v];
    }
    if (!add_edge()) {
      for (int i = 1; i <= m; ++i) printf("0 ");
      printf("\n");
    } else {
      int maxflow = 0;
      while (bfs()) {
        for (int i = s; i <= t; i++) cur[i] = head[i];
        while (int d = dfs(s, 2000000000)) maxflow += d;
      }
      if (maxflow == sum) {
        int id = 0;
        for (int i = 1; i <= n; ++i) {
          if (rd[i] > k) {
            for (int j = head[i]; j != -1; j = e[j].next) {
              int type = e[j].type;
              if (!type) continue;
              if (e[j].w) continue;
              int des = e[j].des;
              ans[des - n] = (++id + 1) / 2;
            }
          }
        }
        id /= 2;
        for (int i = 1; i <= m; ++i)
          if (!ans[i]) ans[i] = ++id;
      }
      for (int i = 1; i <= m; ++i) printf("%d ", ans[i]);
      printf("\n");
    }
  }
  return 0;
}
