#include <bits/stdc++.h>
using namespace std;
template <typename num_t>
inline void addmod(num_t& a, const long long& b, const int& m) {
  a = (a + b) % m;
  if (a < 0) a += m;
}
template <typename num_t>
inline void update_max(num_t& a, const num_t& b) {
  a = max(a, b);
}
template <typename num_t>
inline void update_min(num_t& a, const num_t& b) {
  a = min(a, b);
}
template <typename num_t>
num_t gcd(num_t lhs, num_t rhs) {
  return !lhs ? rhs : gcd(rhs % lhs, lhs);
}
template <typename num_t>
num_t pw(num_t n, num_t k, num_t mod) {
  long long res = 1;
  for (; k; k >>= 1) {
    if (k & 1) res = res * n % mod;
    n = 1ll * n * n % mod;
  }
  return (num_t)res;
}
const int inf = 1e9 + 7;
const long long ll_inf = 1ll * inf * inf;
const int MAX_N = 30000 + 7;
const int mod = 998244353;
template <typename T>
class Dinic {
 public:
  const static int MAXE = 1000007;
  const static int MAXN = 20007;
  const static int inf = 1000000007;
  int adj[MAXE], link[MAXE], head[MAXN], run[MAXN], que[MAXN], level[MAXN];
  T flow[MAXE], cap[MAXE];
  int n, s, t, E;
  bool bfs() {
    for (int i = 0; i < n; ++i) level[i] = -1;
    level[s] = 0;
    int top = 0;
    que[top++] = s;
    for (int i = 0; i < top; ++i) {
      int u = que[i];
      for (int j = head[u]; ~j; j = link[j]) {
        int v = adj[j];
        if (!~level[v] && flow[j] < cap[j]) {
          que[top++] = v;
          level[v] = level[u] + 1;
        }
      }
    }
    return level[t] != -1;
  }
  vector<pair<int, int>> get_min_cut() {
    bfs();
    vector<pair<int, int>> ans;
    for (int j = 0; j < E; j++) {
      int v = adj[j];
      int u = adj[j ^ 1];
      if (flow[j] > 0 && flow[j] == cap[j] && level[u] != -1 &&
          level[v] == -1) {
        ans.push_back({u, v});
      }
    }
    return ans;
  }
  T dfs(int u, T mCap) {
    if (u == t) return mCap;
    for (int& j = run[u]; j != -1; j = link[j]) {
      int v = adj[j];
      T ans = 0;
      if (level[v] == level[u] + 1 && cap[j] > flow[j] &&
          ((ans = dfs(v, min(mCap, cap[j] - flow[j]))) > 0)) {
        flow[j] += ans;
        flow[j ^ 1] -= ans;
        return ans;
      }
    }
    return 0;
  }
  int get_match(int u) {
    for (int& j = run[u]; j != -1; j = link[j]) {
      int v = adj[j];
      if (flow[j] <= 0) continue;
      if (v == t) {
        --flow[j];
        return u;
      } else {
        int res = get_match(v);
        if (res != -1) {
          --flow[j];
          return res;
        }
      }
    }
    return -1;
  }
  void init(int _n, int _s, int _t) {
    n = _n;
    s = _s;
    t = _t;
    E = 0;
    for (int i = 0; i < n; ++i) head[i] = -1;
  }
  void add(int u, int v, T c1, T c2 = 0) {
    adj[E] = v;
    flow[E] = 0;
    cap[E] = c1;
    link[E] = head[u];
    head[u] = E++;
    adj[E] = u;
    flow[E] = 0;
    cap[E] = c2;
    link[E] = head[v];
    head[v] = E++;
  }
  T max_flow() {
    T res = 0;
    while (bfs()) {
      for (int i = 0; i < n; ++i) run[i] = head[i];
      for (T ff = dfs(s, inf); ff > 0; ff = dfs(s, inf)) {
        res += ff;
      }
    }
    return res;
  }
};
Dinic<int> dinic;
int n, m, k;
int deg[MAX_N];
void solve() {
  int test;
  cin >> test;
  while (test-- > 0) {
    cin >> n >> m >> k;
    int tol = n + m, s = tol++, t = tol++;
    dinic.init(tol, s, t);
    fill_n(deg, n, 0);
    for (int j = 0; j < m; ++j) {
      int u, v;
      cin >> u >> v;
      --u;
      --v;
      deg[u]++;
      deg[v]++;
      dinic.add(u, j + n, 1);
      dinic.add(v, j + n, 1);
      dinic.add(j + n, t, 1);
    }
    int max_flow = 0;
    for (int i = 0; i < n; ++i)
      if (deg[i] > k) {
        dinic.add(s, i, 2 * (deg[i] - k));
        max_flow += 2 * (deg[i] - k);
      }
    if (dinic.max_flow() != max_flow) {
      for (int j = (0), _b = (m); j < _b; ++j) cout << 0 << ' ';
      cout << '\n';
      continue;
    }
    vector<vector<int>> edges(n);
    for (int j = 0; j < dinic.E; ++j)
      if (dinic.flow[j] > 0) {
        int v = dinic.adj[j];
        int u = dinic.adj[j ^ 1];
        if (u < n && v >= n && v < n + m) {
          edges[u].push_back(v - n);
        }
      }
    vector<int> ans(m, 0);
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < edges[i].size(); j += 2) {
        ans[edges[i][j]] = ans[edges[i][j + 1]] = ++cnt;
      }
    }
    for (int i = 0; i < m; ++i) {
      if (!ans[i]) ans[i] = ++cnt;
      cout << ans[i] << ' ';
    }
    cout << '\n';
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  const bool multiple_test = false;
  int test = 1;
  if (multiple_test) cin >> test;
  for (int i = 0; i < test; ++i) {
    solve();
  }
}
