#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-9;
const long long oo = 0x3f3f3f3f3f3f3f3fLL;
const int MAXN = 2048;
int DINIC_N, DINIC_SRC, DINIC_DST;
vector<int> adj[MAXN];
unordered_map<int, long long> residual[MAXN];
void reset(int n, int s, int t) {
  assert(n <= MAXN);
  DINIC_N = n, DINIC_SRC = s, DINIC_DST = t;
  for (int i = (0); i < (DINIC_N); i++) adj[i].clear();
  for (int i = (0); i < (DINIC_N); i++) residual[i].clear();
}
void add_edge(int a, int b, long long c) {
  adj[a].push_back(b);
  adj[b].push_back(a);
  residual[a][b] += c;
}
long long dinic_rek(int n, vector<int>& edges_done, vector<int>& dist,
                    long long flow) {
  if (n == DINIC_SRC) return flow;
  while (edges_done[n] < int((adj[n]).size())) {
    long long from = adj[n][edges_done[n]++], cur_flow;
    if (dist[from] + 1 == dist[n] && residual[from][n] > 0) {
      if (0 < (cur_flow = dinic_rek(from, edges_done, dist,
                                    min(flow, residual[from][n])))) {
        if (residual[from][n] -= cur_flow) --edges_done[n];
        residual[n][from] += cur_flow;
        return cur_flow;
      }
    }
  }
  return 0;
}
long long dinic() {
  for (int i = (0); i < (DINIC_N); i++) {
    sort((adj[i]).begin(), (adj[i]).end());
    auto it = unique((adj[i]).begin(), (adj[i]).end());
    adj[i].resize(distance(adj[i].begin(), it));
  }
  long long flow = 0, cur_flow = 0;
  while (true) {
    vector<int> dist(DINIC_N, DINIC_N), edges_done(DINIC_N, 0);
    queue<int> q;
    q.push(DINIC_SRC);
    dist[DINIC_SRC] = 0;
    while (!q.empty()) {
      int n = q.front();
      q.pop();
      if (n == DINIC_DST) break;
      for (auto to : adj[n]) {
        if (residual[n][to] > 0 && dist[to] == DINIC_N) {
          dist[to] = dist[n] + 1;
          q.push(to);
        }
      }
    }
    if (dist[DINIC_DST] == DINIC_N) return flow;
    while (0 < (cur_flow = dinic_rek(DINIC_DST, edges_done, dist, oo))) {
      flow += cur_flow;
    }
  }
}
int edges[MAXN][2];
int edge_color[MAXN];
void calc() {
  int N, M, K;
  cin >> N >> M >> K;
  reset(N + M + 2, 0, N + M + 1);
  for (int m = (N + 1); m < (N + M + 1); m++) {
    cin >> edges[m][0] >> edges[m][1];
    add_edge(0, m, 1);
    add_edge(m, edges[m][0], 1);
    add_edge(m, edges[m][1], 1);
  }
  for (int n = (1); n < (N + 1); n++) {
    int degree = adj[n].size();
    if (degree > K) {
      add_edge(n, N + M + 1, (degree - K) * 2);
    }
  }
  dinic();
  for (int n = (1); n < (N + 1); n++) {
    if (residual[n][N + M + 1] > 0) {
      for (int i = (0); i < (M); i++) cout << 0 << ((i == M - 1) ? "\n" : " ");
      return;
    }
  }
  int COL = 1;
  for (int m = (N + 1); m < (N + M + 1); m++) {
    if (residual[0][m] > 0) {
      edge_color[m] = COL++;
    }
  }
  bool first = true;
  for (int n = (1); n < (N + 1); n++) {
    for (auto eid : adj[n])
      if (residual[n][eid]) {
        edge_color[eid] = COL;
        if (!first) COL++;
        first = !first;
      }
  }
  for (int m = (N + 1); m < (N + M + 1); m++)
    cout << edge_color[m] << ((m == N + M) ? "\n" : " ");
}
int main() {
  int TC;
  cin >> TC;
  while (TC--) calc();
}
