#include <bits/stdc++.h>
using namespace std;
struct Edge {
  int to;
  int cap, flow;
  size_t rev;
  int r() const { return cap - flow; }
  bool pos() const { return cap > flow; }
  Edge() : flow(0) {}
  Edge(int to, int cap, size_t rev) : to(to), cap(cap), rev(rev), flow(0) {}
};
struct MaxFlowGraph {
  int n, source, sink;
  vector<vector<Edge> > g;
  vector<int> vis;
  int hvis;
  MaxFlowGraph() {}
  MaxFlowGraph(int n, int s, int t) : n(n), source(s), sink(t), g(n), vis(n) {}
  void addEdge(int from, int to, int cap) {
    size_t p1 = g[from].size(), p2 = g[to].size();
    g[from].push_back(Edge(to, cap, p2));
    g[to].push_back(Edge(from, 0, p1));
  }
  int find() {
    hvis = 0;
    int res = 0, delta;
    do {
      hvis++;
      delta = dfs(source);
      res += delta;
    } while (delta);
    return res;
  }
  int dfs(int v, int t = (1 << 30)) {
    if (v == sink) return t;
    if (vis[v] == hvis) return 0;
    vis[v] = hvis;
    int sz = g[v].size();
    for (int i = (0); i < (sz); ++i) {
      Edge& e = g[v][i];
      if (e.pos()) {
        if (int delta = dfs(e.to, min(e.r(), t))) {
          e.flow += delta;
          g[e.to][e.rev].flow -= delta;
          return delta;
        }
      }
    }
    return 0;
  }
};
int res[1000];
int deg[1000];
void solve() {
  int n, m, k;
  scanf("%d %d", &n, &m);
  scanf("%d", &k);
  memset(deg, 0, sizeof deg);
  int OFF_E = 0;
  int OFF_V = m;
  int source = OFF_V + n;
  int sink = source + 1;
  MaxFlowGraph g(sink + 1, source, sink);
  for (int i = (0); i < (m); ++i) {
    int a, b;
    scanf("%d %d", &a, &b);
    --a;
    --b;
    g.addEdge(i, OFF_V + a, 1);
    g.addEdge(i, OFF_V + b, 1);
    ++deg[a];
    ++deg[b];
  }
  int expected_flow = 0;
  for (int i = (0); i < (n); ++i)
    if (deg[i] > k) {
      int cap = 2 * (deg[i] - k);
      expected_flow += cap;
      g.addEdge(OFF_V + i, sink, cap);
    }
  for (int i = (0); i < (m); ++i) g.addEdge(source, i, 1);
  int flow = g.find();
  if (flow != expected_flow) {
    for (int i = (0); i < (m); ++i) printf("0 ");
    puts("");
    return;
  }
  for (int i = (0); i < (m); ++i) res[i] = i + 1;
  vector<vector<int> > groups(n);
  for (int e = (0); e < (m); ++e)
    for (Edge& edge : g.g[e])
      if (edge.flow > 0) groups[edge.to - OFF_V].push_back(e);
  for (int i = (0); i < (n); ++i) {
    for (int p = 0; p < groups[i].size(); p += 2)
      res[groups[i][p + 1]] = res[groups[i][p]];
  }
  for (int i = (0); i < (m); ++i) printf("%d ", res[i]);
  puts("");
}
int main() {
  int tc;
  scanf("%d", &tc);
  while (tc--) solve();
}
