#include <bits/stdc++.h>
using namespace std;
template <typename G1, typename G2 = G1, typename G3 = G1>
struct triple {
  G1 first;
  G2 second;
  G3 T;
};
template <typename C, typename R = C, bool lb = false>
struct dinic {
  static_assert(std::is_arithmetic<C>::value, "flow_type must be arithmetic");
  static_assert(std::is_arithmetic<R>::value, "result_type must be arithmetic");
  static const C oo = std::numeric_limits<C>::max();
  struct edge {
    int src;
    int dst;
    int rev;
    C cap, flow;
    edge(int src, int dst, int rev, C cap, C flow)
        : src(src), dst(dst), rev(rev), cap(cap), flow(flow) {}
  };
  dinic(int n)
      : adj(n + 2 * lb),
        que(n + 2 * lb),
        level(n + 2 * lb),
        edge_pos(n + 2 * lb) {}
  int add_edge(int src, int dst, C cap, C rcap = 0) {
    adj[src].emplace_back(src, dst, (int)adj[dst].size(), cap, lb ? rcap : 0);
    if (src == dst) adj[src].back().rev++;
    adj[dst].emplace_back(dst, src, (int)adj[src].size() - 1, lb ? 0 : rcap, 0);
    return (int)adj[src].size() - 1 - (src == dst);
  }
  inline bool side_of_S(int u) { return level[u] == -1; }
  R max_flow(int source, int sink) {
    R flow = 0;
    while (true) {
      int front = 0, back = 0;
      std::fill(level.begin(), level.end(), -1);
      for (level[que[back++] = sink] = 0; front < back && level[source] == -1;
           ++front) {
        int u = que[front];
        for (const edge &e : adj[u])
          if (level[e.dst] == -1 && rev(e).flow < rev(e).cap)
            level[que[back++] = e.dst] = 1 + level[u];
      }
      if (level[source] == -1) break;
      std::fill(edge_pos.begin(), edge_pos.end(), 0);
      std::function<C(int, C)> find_path = [&](int from, C res) {
        if (from == sink) return res;
        for (int &ept = edge_pos[from]; ept < (int)adj[from].size(); ++ept) {
          edge &e = adj[from][ept];
          if (e.flow == e.cap || level[e.dst] + 1 != level[from]) continue;
          C push = find_path(e.dst, std::min(res, e.cap - e.flow));
          if (push > 0) {
            e.flow += push;
            rev(e).flow -= push;
            if (e.flow == e.cap) ++ept;
            return push;
          }
        }
        return static_cast<C>(0);
      };
      for (C f; (f = find_path(source, oo)) > 0;) flow += f;
    }
    return flow;
  }
  R max_flow_lb(int source, int sink) {
    int n = adj.size() - 2;
    vector<C> delta(n + 2);
    for (int u = 0; u < n; ++u)
      for (auto &e : adj[u]) {
        delta[u] -= e.flow;
        delta[e.dst] += e.flow;
      }
    R sum = 0;
    int s = n, t = n + 1;
    for (int u = 0; u < n; ++u) {
      if (delta[u] > 0) {
        add_edge(s, u, delta[u], 0);
        sum += delta[u];
      } else if (delta[u] < 0)
        add_edge(u, t, -delta[u], 0);
    }
    add_edge(sink, source, oo, 0);
    if (max_flow(s, t) != sum) return -1;
    R flow = adj[sink].back().flow;
    adj[sink].pop_back();
    adj[source].pop_back();
    return flow + max_flow(source, sink);
  }
  std::vector<std::vector<edge>> adj;

 private:
  std::vector<int> que;
  std::vector<int> level;
  std::vector<int> edge_pos;
  inline edge &rev(const edge &e) { return adj[e.dst][e.rev]; }
};
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int test;
  cin >> test;
  while (test--) {
    int n, m, k;
    cin >> n >> m >> k;
    vector<triple<int>> ed(m);
    vector<int> deg(n);
    for (auto &i : ed) {
      cin >> i.first >> i.second;
      --i.first;
      --i.second;
      ++deg[i.first];
      ++deg[i.second];
    }
    dinic<int> d(n + m + 2);
    int source = n + m, sink = n + m + 1;
    vector<triple<int>> temp;
    for (int i = 0; i < m; i++) {
      int h = d.add_edge(ed[i].first, i + n, 1);
      temp.push_back({ed[i].first, i, h});
      h = d.add_edge(ed[i].second, i + n, 1);
      temp.push_back({ed[i].second, i, h});
      d.add_edge(i + n, sink, 1);
    }
    int f = 0;
    for (int i = 0; i < n; i++)
      if (deg[i] > k) {
        d.add_edge(source, i, 2 * (deg[i] - k));
        f += 2 * (deg[i] - k);
      }
    if (d.max_flow(source, sink) != f) {
      for (int i = 0; i < m; i++) cout << 0 << " \n"[i == m - 1];
      continue;
    }
    vector<vector<int>> g(n);
    for (auto i : temp)
      if (d.adj[i.first][i.T].flow) g[i.first].push_back(i.second);
    int t = 1;
    vector<int> ans(m);
    for (auto i : g)
      for (int j = 0; j < i.size(); j += 2) ans[i[j]] = ans[i[j + 1]] = t++;
    for (auto &i : ans)
      if (i == 0) i = t++;
    for (int i = 0; i < m; i++) cout << ans[i] << " \n"[i == m - 1];
  }
  return 0;
}
