#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
mt19937_64 mt_rand(chrono::system_clock::now().time_since_epoch().count());
template <typename T1, typename T2>
inline bool upmax(T1& a, T2 b) {
  return (a < b ? (a = b, true) : false);
}
template <typename T1, typename T2>
inline bool upmin(T1& a, T2 b) {
  return (b < a ? (a = b, true) : false);
}
const int maxn = (int)1e6 + 20;
const int maxlog = 21;
const int base = (int)1e9 + 7;
const long double eps = (long double)1e-7;
const long double PI = acos(-1.);
struct Edge {
  int u, v;
  long long cap, flow;
  Edge() {}
  Edge(int u, int v, long long cap) : u(u), v(v), cap(cap), flow(0) {}
};
struct Dinic {
  int N;
  vector<Edge> E;
  vector<vector<int>> g;
  vector<int> d, pt;
  Dinic(int N) : N(N), E(0), g(N), d(N), pt(N) {}
  void AddEdge(int u, int v, long long cap) {
    if (u != v) {
      E.emplace_back(Edge(u, v, cap));
      g[u].emplace_back(E.size() - 1);
      E.emplace_back(Edge(v, u, 0));
      g[v].emplace_back(E.size() - 1);
    }
  }
  bool BFS(int S, int T) {
    queue<int> q({S});
    fill(d.begin(), d.end(), N + 1);
    d[S] = 0;
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      if (u == T) break;
      for (int k : g[u]) {
        Edge& e = E[k];
        if (e.flow < e.cap && d[e.v] > d[e.u] + 1) {
          d[e.v] = d[e.u] + 1;
          q.emplace(e.v);
        }
      }
    }
    return d[T] != N + 1;
  }
  long long DFS(int u, int T, long long flow = -1) {
    if (u == T || flow == 0) return flow;
    for (int& i = pt[u]; i < g[u].size(); ++i) {
      Edge& e = E[g[u][i]];
      Edge& oe = E[g[u][i] ^ 1];
      if (d[e.v] == d[e.u] + 1) {
        long long amt = e.cap - e.flow;
        if (flow != -1 && amt > flow) amt = flow;
        if (long long pushed = DFS(e.v, T, amt)) {
          e.flow += pushed;
          oe.flow -= pushed;
          return pushed;
        }
      }
    }
    return 0;
  }
  long long MaxFlow(int S, int T) {
    long long total = 0;
    while (BFS(S, T)) {
      fill(pt.begin(), pt.end(), 0);
      while (long long flow = DFS(S, T)) total += flow;
    }
    return total;
  }
};
int ans[601];
pair<int, int> pr[maxn];
vector<pair<int, int>> g[601];
void solve() {
  memset(ans, 0, sizeof(ans));
  int n, m, k;
  cin >> n >> m >> k;
  for (int i = 1; i <= n; i++) g[i].clear();
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    g[a].push_back(make_pair(a, i + 1));
    g[b].push_back(make_pair(b, i + 1));
  }
  int s = 0;
  int t = m + n + 1;
  vector<pair<int, pair<int, int>>> edges;
  int sum = 0;
  for (int i = 1; i <= n; i++) {
    sum += max(0, (int)g[i].size() - k);
    edges.push_back(
        make_pair(2 * max(0, (int)g[i].size() - k), make_pair(s, i)));
  }
  for (int i = 1; i <= m; i++) {
    edges.push_back(make_pair(1, make_pair(i + n, t)));
  }
  int cnt = m + n + 2;
  for (int i = 1; i <= n; i++)
    for (int j = 0; j < g[i].size(); j++)
      for (int k = j + 1; k < g[i].size(); k++) {
        int u = g[i][j].first, v = g[i][k].first;
        int iu = g[i][j].second, iv = g[i][k].second;
        if (u > v) swap(u, v);
        pr[cnt] = make_pair(iu, iv);
        edges.push_back(make_pair(2, make_pair(i, cnt)));
        edges.push_back(make_pair(1, make_pair(cnt, iu + n)));
        edges.push_back(make_pair(1, make_pair(cnt, iv + n)));
        cnt++;
      }
  Dinic flow(cnt + 5);
  for (auto e : edges) {
    flow.AddEdge(e.second.first, e.second.second, e.first);
  }
  int res = flow.MaxFlow(s, t);
  if (res != sum * 2) {
    for (int i = 0; i < m; i++) cout << 0 << ' ';
    cout << "\n";
    return;
  }
  vector<pair<int, int>> asd;
  for (int i = 1; i <= n; i++) {
    vector<int> v;
    for (int j = 0; j < flow.g[i].size(); j++) {
      Edge e = flow.E[flow.g[i][j]];
      if (e.flow == 1) {
        int pr = e.v;
        for (auto k : flow.g[pr]) {
          Edge e2 = flow.E[k];
          if (e2.flow == 1) {
            v.push_back(e2.v - n);
          }
        }
      } else if (e.flow == 2) {
        asd.push_back(pr[e.v]);
      }
    }
    assert(v.size() % 2 == 0);
    for (int j = 0; j < v.size(); j += 2) {
      asd.push_back(make_pair(v[j], v[j + 1]));
    }
  }
  int kek = 1;
  for (auto e : asd) {
    ans[e.first] = ans[e.second] = kek++;
  }
  for (int i = 1; i <= m; i++) {
    if (!ans[i]) ans[i] = kek++;
    cout << ans[i] << ' ';
  }
  cout << "\n";
}
int main() {
  int t;
  cin >> t;
  while (t--) solve();
}
