#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 9999;
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) {}
  } edges[N];
  int n, s, t, E, head[N];
  bool vis[N];
  int d[N], cur[N];
  vector<int> vec[N];
  int ans[N];
  inline void AddEdge(int f, int t, int c) {
    edges[++E] = Edge(f, t, c, 0, head[f]);
    head[f] = E;
    edges[++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++) vec[i].clear();
    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 != -1; i = nxt) {
        Edge& e = edges[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 != -1; i = nxt) {
      Edge& e = edges[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;
      edges[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;
  }
  inline void solve(int n, int m) {
    for (int x = 1; x <= m; x++)
      for (int nxt, i = head[x]; i != -1; i = nxt) {
        Edge& e = edges[i];
        nxt = e.nxt;
        if (e.flow == 1) vec[e.to - m].push_back(x);
      }
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
      cnt++;
      for (int j = 0; j < vec[i].size(); j++) {
        if (j % 2 == 0)
          ans[vec[i][j]] = cnt;
        else
          ans[vec[i][j]] = cnt++;
      }
    }
    for (int i = 1; i <= m; i++) printf("%d%c", ans[i], i == m ? '\n' : ' ');
  }
} g;
int main() {
  int cas, n, m, k, x, y;
  scanf("%d", &cas);
  while (cas--) {
    scanf("%d%d%d", &n, &m, &k);
    int s = 0, t = n + m + 1;
    g.Init(t + 1, s, t);
    for (int i = 1; i <= m; i++) {
      scanf("%d%d", &x, &y);
      g.AddEdge(i, x + m, 2);
      g.AddEdge(i, y + m, 2);
      g.AddEdge(s, i, 3);
    }
    for (int i = 1; i <= n; i++) g.AddEdge(i + m, t, 2 * k);
    int ma = g.maxFlow();
    if (ma != 3 * m) {
      for (int i = 1; i <= m; i++) printf("0%c", i == m ? '\n' : ' ');
      continue;
    }
    g.solve(n, m);
  }
}
