#include <bits/stdc++.h>
using namespace std;
int N, M, K;
int S, T;
pair<int, int> edge[1205];
int choosen[606];
int deg[606];
vector<int> match[606];
int ans[605];
vector<int> adj[1205];
int cap[1205][1205];
int par[1205];
int p_color = 0;
const int inf = 1e9;
void make_edge(int u, int v, int cf, int cb) {
  cap[u][v] = cf;
  cap[v][u] = cb;
  adj[u].push_back(v);
  adj[v].push_back(u);
}
int bfs() {
  memset(par, -1, sizeof(par));
  queue<pair<int, int> > q;
  q.emplace(S, inf);
  par[S] = -2;
  while (!q.empty()) {
    int u = q.front().first;
    int flow = q.front().second;
    q.pop();
    for (int v : adj[u]) {
      if (par[v] == -1 && cap[u][v] > 0) {
        par[v] = u;
        int new_flow = min(flow, cap[u][v]);
        if (v == T) return new_flow;
        q.emplace(v, new_flow);
      }
    }
  }
  return 0;
}
int maxflow() {
  int flow = 0, new_flow;
  while (new_flow = bfs()) {
    flow += new_flow;
    int u = T;
    while (u != S) {
      cap[par[u]][u] -= new_flow;
      cap[u][par[u]] += new_flow;
      u = par[u];
    }
  }
  return flow;
}
void clean() {
  memset(cap, 0, sizeof(cap));
  memset(deg, 0, sizeof(deg));
  memset(choosen, 0, sizeof(choosen));
  for (int i = 1; i <= 1202; i++) {
    adj[i].clear();
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  int tc;
  cin >> tc;
  while (tc--) {
    cin >> N >> M >> K;
    clean();
    S = 0, T = N + M + 1;
    int u, v;
    for (int i = 1; i <= M; i++) {
      cin >> u >> v;
      make_edge(u, N + i, 1, 0);
      make_edge(v, N + i, 1, 0);
      make_edge(N + i, T, 1, 0);
      deg[u]++, deg[v]++;
    }
    bool ok = 1;
    int total_need = 0, need = 0;
    for (int i = 1; i <= N; i++) {
      if (deg[i] > 2 * K) ok = false;
      if (deg[i] > K) {
        need = (deg[i] - K) * 2;
        total_need += need;
        make_edge(S, i, need, 0);
      }
    }
    int flow = maxflow();
    if (!ok || flow < total_need) {
      for (int i = 1; i <= M; i++) cout << choosen[i] << " ";
      cout << "\n";
      ;
      continue;
    }
    int last = 0;
    for (int i = 1; i <= N; i++) {
      for (int v : adj[i]) {
        if (cap[v][i] == 1) {
          if (last) {
            choosen[v - N] = last;
            last = 0;
          } else {
            choosen[v - N] = ++p_color;
            last = p_color;
          }
        }
      }
    }
    for (int i = 1; i <= N; i++) {
      for (int v : adj[i]) {
        if (!choosen[v - N]) {
          choosen[v - N] = ++p_color;
        }
      }
    }
    for (int i = 1; i <= M; i++) cout << choosen[i] << " ";
    cout << "\n";
    ;
  }
}
