#include <bits/stdc++.h>
using namespace std;
struct mf {
  struct edge {
    int to, flow, back;
    edge(int a, int b, int c) : to(a), flow(b), back(c) {}
  };
  int n, s, t, ans, now;
  vector<vector<edge>> v;
  vector<int> at, ver, dis;
  queue<int> q;
  void init(int a, int b, int c) {
    n = a;
    v = vector<vector<edge>>(n, vector<edge>());
    at = ver = dis = vector<int>(n, 0);
    s = b;
    t = c;
    ans = 0;
    q = queue<int>();
  }
  void bd(int a, int b, int c) {
    v[a].emplace_back(b, c, v[b].size());
    v[b].emplace_back(a, 0, v[a].size() - 1);
  }
  void bd(int a, int b) { bd(a, b, 1); }
  int dfs(int a, int b) {
    if (a == t) return b;
    for (int& i = at[a]; i < v[a].size(); i++)
      if (ver[v[a][i].to] == now && v[a][i].flow &&
          dis[v[a][i].to] == dis[a] + 1) {
        int re = dfs(v[a][i].to, min(v[a][i].flow, b));
        if (re) {
          b -= re;
          v[a][i].flow -= re;
          v[v[a][i].to][v[a][i].back].flow += re;
          return re;
        }
      }
    return 0;
  }
  void bfs() {
    for (now = 1;; now++) {
      q.push(s);
      ver[s] = now;
      at[s] = dis[s] = 0;
      while (!q.empty()) {
        int tmp = q.front();
        q.pop();
        for (auto j : v[tmp])
          if (j.flow) {
            int to = j.to;
            if (ver[to] != now) {
              ver[to] = now;
              at[to] = 0;
              dis[to] = dis[tmp] + 1;
              q.push(to);
            };
          }
      }
      if (ver[t] != now) return;
      while (1) {
        int tmp = dfs(s, INT_MAX);
        if (tmp)
          ans += tmp;
        else
          break;
      }
    }
  }
} mf;
int t, n, m, k, cnt[605], ans[605];
vector<int> vv[605];
bool gg;
int ta, tb;
int main() {
  scanf("%d", &t);
  while (t--) {
    scanf("%d%d%d", &n, &m, &k);
    mf.init(n + m + 2, n + m, n + m + 1);
    for (int i = 0; i < n; i++) {
      cnt[i] = 0;
      vv[i].clear();
    }
    for (int i = 0; i < m; i++) {
      ans[i] = i;
      scanf("%d%d", &ta, &tb);
      ta--;
      tb--;
      mf.bd(ta, n + i);
      mf.bd(tb, n + i);
      mf.bd(n + i, mf.t);
      cnt[ta]++;
      cnt[tb]++;
      vv[ta].push_back(i);
      vv[tb].push_back(i);
    }
    for (int i = 0; i < n; i++) mf.bd(mf.s, i, max(0, (cnt[i] - k) * 2));
    mf.bfs();
    gg = 0;
    for (auto& i : mf.v[mf.s])
      if (i.flow) {
        gg = 1;
        break;
      }
    ta = -1;
    for (int i = 0; i < n; i++)
      for (int j = 0; j < vv[i].size(); j++)
        if (mf.v[i][j].flow == 0)
          if (ta == -1)
            ta = vv[i][j];
          else {
            ans[vv[i][j]] = ta;
            ta = -1;
          }
    if (gg)
      for (int i = 0; i < m; i++) ans[i] = -1;
    for (int i = 0; i < m; i++)
      printf("%d%c", ans[i] + 1, i == m - 1 ? '\n' : ' ');
  }
  return 0;
}
