#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int now = 0;
  register char c = getchar();
  for (; !isdigit(c); c = getchar())
    ;
  for (; isdigit(c); now = now * 10 + c - '0', c = getchar())
    ;
  return now;
}
const double eps = 1e-9;
const int maxn = 4010;
const int maxm = 20000;
const long long INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
struct Dinic {
  struct Edge {
    int from, to, cap, flow, nxt;
    Edge() {}
    Edge(int u, int v, int c, int f, int n)
        : from(u), to(v), cap(c), flow(f), nxt(n) {}
  } edge[maxm];
  int n, s, t, E, head[maxn];
  bool vis[maxn];
  int d[maxn], cur[maxn];
  inline void AddEdge(int f, int t, int c) {
    edge[++E] = Edge(f, t, c, 0, head[f]);
    head[f] = E;
    edge[++E] = Edge(t, f, 0, 0, head[t]);
    head[t] = E;
  }
  inline void Init(int n, int s, int t) {
    this->n = n;
    E = -1;
    this->s = s;
    head[s] = -1;
    this->t = t;
    head[t] = -1;
    for (int i = 0; i <= n; i++) head[i] = -1;
  }
  inline bool BFS() {
    memset(vis, 0, sizeof(vis));
    queue<int> Q;
    d[s] = 0;
    vis[s] = 1;
    for (Q.push(s); !Q.empty();) {
      int x = Q.front();
      Q.pop();
      for (int nxt, i = head[x]; ~i; i = nxt) {
        Edge &e = edge[i];
        nxt = e.nxt;
        if (vis[e.to] || e.cap <= e.flow) continue;
        vis[e.to] = 1;
        d[e.to] = d[x] + 1;
        Q.push(e.to);
      }
    }
    return vis[t];
  }
  inline int DFS(const int &x, int a) {
    if (x == t || a == 0) return a;
    int flow = 0, f, nxt;
    for (int &i = cur[x]; ~i; i = nxt) {
      Edge &e = edge[i];
      nxt = e.nxt;
      if (d[x] + 1 != d[e.to]) continue;
      f = DFS(e.to, min(a, e.cap - e.flow));
      if (f <= 0) continue;
      e.flow += f;
      edge[i ^ 1].flow -= f;
      flow += f;
      a -= f;
      if (!a) break;
    }
    return flow;
  }
  inline int maxFlow() { return maxFlow(s, t); }
  inline int maxFlow(int s, int t) {
    int flow = 0;
    for (; BFS();) {
      for (int i = 0; i <= n; i++) cur[i] = head[i];
      flow += DFS(s, INF);
    }
    return flow;
  }
} g;
int N, M, K;
struct Edge {
  int to, next;
} edge[maxn * 2];
int head[maxn], tot;
int ind[maxn];
int id[maxn];
void init() {
  tot = 0;
  for (int i = 1; i <= M; i++) id[i] = 0;
  for (int i = 1; i <= N; i++) ind[i] = 0, head[i] = -1;
}
void add(int u, int v) {
  edge[tot].to = v;
  edge[tot].next = head[u];
  head[u] = tot++;
}
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%d%d%d", &N, &M, &K);
    init();
    for (int i = 1; i <= M; i++) {
      int u, v;
      scanf("%d%d", &u, &v);
      ind[u]++;
      ind[v]++;
      add(u, i + N);
      add(v, i + N);
    }
    int s = N + M + 2, t = N + M + 1;
    g.Init(t + 2, s, t);
    bool flag = 1;
    int sum = 0;
    for (int i = 1; i <= N && flag; i++) {
      if (ind[i] > 2 * K) flag = 0;
      g.AddEdge(s, i, max(2 * (ind[i] - K), 0));
      sum += 2 * max((ind[i] - K), 0);
      for (int j = head[i]; ~j; j = edge[j].next) {
        int v = edge[j].to;
        g.AddEdge(i, v, 1);
      }
    }
    if (!flag) {
      for (int i = 1; i <= M; i++) {
        printf("0 ");
      }
      puts("");
      continue;
    }
    for (int i = N + 1; i <= N + M; i++) {
      g.AddEdge(i, t, 1);
    }
    if (g.maxFlow() != sum) {
      for (int i = 1; i <= M; i++) {
        printf("0 ");
      }
      puts("");
      continue;
    }
    int cnt = 1;
    for (int i = 1; i <= N; i++) {
      int num = 0;
      for (int j = g.head[i]; ~j; j = g.edge[j].nxt) {
        if (g.edge[j].flow) {
          id[g.edge[j].to - N] = cnt;
          num++;
          if (num == 2) {
            cnt++;
            num = 0;
          }
        }
      }
    }
    for (int i = 1; i <= N; i++) {
      for (int j = head[i]; ~j; j = edge[j].next) {
        int v = edge[j].to;
        v -= N;
        if (id[v]) continue;
        id[v] = cnt++;
      }
    }
    for (int i = 1; i <= M; i++) {
      printf("%d ", id[i]);
    }
    puts("");
  }
  return 0;
}
