#include <bits/stdc++.h>
using namespace std;
const int N = 650, INF = 1e9;
struct Dinic {
  int nodes, src, dst;
  vector<int> dist, q, work;
  struct edge {
    int to, rev;
    long long f, cap;
  };
  vector<vector<edge>> g;
  Dinic(int x) : nodes(x), g(x), dist(x), q(x), work(x) {}
  void add_edge(int s, int t, long long cap) {
    g[s].push_back((edge){t, int(g[t].size()), 0, cap});
    g[t].push_back((edge){s, int(g[s].size()) - 1, 0, 0});
  }
  bool dinic_bfs() {
    fill(dist.begin(), dist.end(), -1);
    dist[src] = 0;
    int qt = 0;
    q[qt++] = src;
    for (int qh = 0; qh < qt; qh++) {
      int u = q[qh];
      for (int i = 0; i < int(g[u].size()); ++i) {
        edge &e = g[u][i];
        int v = g[u][i].to;
        if (dist[v] < 0 && e.f < e.cap) dist[v] = dist[u] + 1, q[qt++] = v;
      }
    }
    return dist[dst] >= 0;
  }
  long long dinic_dfs(int u, long long f) {
    if (u == dst) return f;
    for (int &i = work[u]; i < int(g[u].size()); ++i) {
      edge &e = g[u][i];
      if (e.cap <= e.f) continue;
      int v = e.to;
      if (dist[v] == dist[u] + 1) {
        long long df = dinic_dfs(v, min(f, e.cap - e.f));
        if (df > 0) {
          e.f += df;
          g[v][e.rev].f -= df;
          return df;
        }
      }
    }
    return 0;
  }
  long long max_flow(int _src, int _dst) {
    src = _src;
    dst = _dst;
    long long result = 0;
    while (dinic_bfs()) {
      fill(work.begin(), work.end(), 0);
      while (long long delta = dinic_dfs(src, INF)) result += delta;
    }
    return result;
  }
};
vector<int> adj[N];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 0; i < int(n + 1); ++i) adj[i].clear();
    for (int i = 0; i < m; ++i) {
      int a, b;
      cin >> a >> b;
      a--;
      b--;
      adj[a].push_back(i);
      adj[b].push_back(i);
    }
    bool end = false;
    for (int i = 0; i < n; ++i) {
      if (int(adj[i].size()) > 2 * k) end = true;
    }
    if (end) {
      for (int i = 0; i < int(m); ++i) cout << 0 << " ";
      cout << '\n';
      continue;
    }
    int lim = n + m + 5;
    Dinic flow(lim);
    int s = --lim;
    int t = --lim;
    int exp = 0;
    for (int i = 0; i < n; ++i) {
      int deg = int(adj[i].size());
      if (deg <= k) continue;
      exp += 2 * (deg - k);
      flow.add_edge(s, i, 2 * (deg - k));
      for (int j : adj[i]) {
        flow.add_edge(i, n + j, 1);
      }
    }
    for (int i = 0; i < m; ++i) {
      flow.add_edge(n + i, t, 1);
    }
    auto mxflow = flow.max_flow(s, t);
    vector<int> ans(m, 0);
    if (exp == mxflow) {
      int now = 1, end = 10000;
      for (int u = 0; u < n; ++u) {
        int deg = int(adj[u].size());
        if (deg <= k) {
          for (int id : adj[u]) {
            if (ans[id] == 0) ans[id] = now++;
          }
          continue;
        }
        int flag = 1;
        for (auto edge : flow.g[u]) {
          int to = edge.to;
          int f = edge.f;
          if (to == s) continue;
          if (f == 0) {
            int id = to - n;
            if (ans[id] == 0) ans[id] = end--;
          } else {
            int id = to - n;
            ans[id] = now;
            flag ^= 1;
            if (flag) now++;
          }
        }
      }
    }
    for (int i = 0; i < m; ++i) {
      cout << ans[i] << " ";
    }
    cout << '\n';
  }
  return 0;
}
