#include <bits/stdc++.h>
using namespace std;
const int N = 1500;
struct edge {
  int to, cap, flow;
};
vector<edge> es;
vector<int> g[N];
bool used[N];
void init(int n) {
  es.clear();
  for (int i = 0; i < n; i++) g[i].clear();
}
void addEdge(int from, int to, int cap) {
  g[from].push_back(es.size());
  es.push_back({to, cap, 0});
  g[to].push_back(es.size());
  es.push_back({from, 0, 0});
}
bool dfs(int v, int t) {
  used[v] = true;
  if (v == t) return true;
  for (auto i : g[v]) {
    int u = es[i].to, diff = es[i].cap - es[i].flow;
    if (!used[u] && diff > 0 && dfs(u, t)) {
      es[i].flow++;
      es[i ^ 1].flow--;
      return true;
    }
  }
  return false;
}
int maxFlow(int s, int t) {
  int res = 0;
  while (true) {
    fill(used, used + t + 1, false);
    if (dfs(s, t)) {
      res++;
      continue;
    }
    break;
  }
  return res;
}
void printZeros(int n) {
  for (int i = 0; i < n; i++) cout << 0 << ' ';
  cout << endl;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests;
  cin >> tests;
  while (tests--) {
    int n, m, k;
    cin >> n >> m >> k;
    vector<pair<int, int>> _es;
    vector<int> deg(n);
    for (int i = 0; i < m; i++) {
      int v, u;
      cin >> v >> u;
      v--, u--;
      _es.push_back({v, u});
      deg[v]++, deg[u]++;
    }
    bool ok = true;
    for (int v = 0; v < n; v++) ok &= (deg[v] <= 2 * k);
    if (!ok) {
      printZeros(m);
      continue;
    }
    int s = m + n, t = m + n + 1, wantFlow = 0;
    init(t + 1);
    for (int i = 0; i < m; i++) {
      int v = _es[i].first, u = _es[i].second;
      addEdge(s, i, 1);
      addEdge(i, m + v, 1);
      addEdge(i, m + u, 1);
    }
    for (int v = 0; v < n; v++)
      if (deg[v] > k) {
        wantFlow += 2 * (deg[v] - k);
        addEdge(m + v, t, 2 * (deg[v] - k));
      }
    if (maxFlow(s, t) < wantFlow) {
      printZeros(m);
      continue;
    }
    vector<vector<int>> groups(n);
    for (int v = 0; v < m; v++) {
      for (auto i : g[v]) {
        int u = es[i].to, flow = es[i].flow;
        if (u != s && flow > 0) groups[u - m].push_back(v);
      }
    }
    vector<int> ans(m);
    int c = 1;
    for (auto group : groups)
      for (int i = 0; i < group.size(); i += 2)
        ans[group[i]] = ans[group[i + 1]] = c++;
    for (int i = 0; i < m; i++) cout << (ans[i] ? ans[i] : c++) << ' ';
    cout << endl;
  }
}
