#include <bits/stdc++.h>
using namespace std;
struct Edge {
  int from, to, cap;
};
namespace Flow {
vector<Edge> edges;
vector<int> adia[2010];
bool viz[2010];
void reset(int n) {
  edges.clear();
  for (int i = 0; i <= n; i++) adia[i].clear();
}
void add_edge(int from, int to, int cap) {
  adia[from].push_back(edges.size());
  edges.push_back({from, to, cap});
  adia[to].push_back(edges.size());
  edges.push_back({to, from, 0});
}
bool go(int s, int t, int c) {
  if (viz[s]) return false;
  viz[s] = 1;
  if (s == t) return true;
  for (auto i : adia[s]) {
    if (edges[i].cap >= c && go(edges[i].to, t, c)) {
      edges[i].cap -= c;
      edges[i ^ 1].cap += c;
      return true;
    }
  }
  return false;
}
int max_flow(int s, int t) {
  int f = 0, c = 1e9;
  while (c) {
    memset(viz, 0, sizeof viz);
    if (go(s, t, c))
      f += c;
    else
      c /= 2;
  }
  return f;
}
}  // namespace Flow
int grad[1001];
void test() {
  memset(grad, 0, sizeof grad);
  int n, m, k, a, b;
  cin >> n >> m >> k;
  for (int i = 1; i <= m; i++) {
    cin >> a >> b;
    Flow::add_edge(i + n, a, 1);
    Flow::add_edge(i + n, b, 1);
    Flow::add_edge(0, i + n, 1);
    grad[a]++, grad[b]++;
  }
  int s = 0, d = n + m + 1, suma = 0;
  bool mere = 1;
  for (int i = 1; i <= n; i++) {
    int trb = 2 * max(grad[i] - k, 0);
    if (trb > grad[i]) mere = 0;
    if (trb) Flow::add_edge(i, d, trb), suma += trb;
  }
  bool ok = (Flow::max_flow(s, d) == suma) & mere;
  if (!ok) {
    for (int i = 1; i <= m; i++) cout << 0 << ' ';
    cout << '\n';
  } else {
    vector<int> ans(m + 1);
    int cnt = 1, act = 0;
    for (int nod = 1; nod <= n; nod++) {
      for (auto vecin : Flow::adia[nod]) {
        if (Flow::edges[vecin].cap == 1) {
          int x = Flow::edges[vecin].to;
          assert(x >= n && x <= n + m);
          ans[Flow::edges[vecin].to - n] = cnt, cnt += act, act = 1 - act;
        }
      }
    }
    for (int i = 1; i <= m; i++) cout << (ans[i] ? ans[i] : ++cnt) << ' ';
  }
  Flow::reset(d);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) test();
  return 0;
}
