#include <bits/stdc++.h>
using namespace std;
const signed long long llf = (signed long long)(~0ull >> 1);
const signed int inf = (signed)(~0u >> 1);
template <typename T>
T __abs(T x) {
  return (x < 0) ? (-x) : (x);
}
template <typename T>
void pfill(T* pst, const T* ped, T val) {
  for (; pst != ped; *(pst++) = val)
    ;
}
template <typename T>
void pcopy(T* pst, const T* ped, T* pv) {
  for (; pst != ped; *(pst++) = *(pv++))
    ;
}
typedef class Edge {
 public:
  int ed, nx, cap, f;
  Edge() {}
  Edge(int ed, int nx, int cap, int f) : ed(ed), nx(nx), cap(cap), f(f) {}
} Edge;
typedef class MapManager {
 public:
  int* h;
  vector<Edge> es;
  MapManager() {}
  MapManager(int n) {
    h = new int[(n + 1)];
    pfill(h, h + n + 1, -1);
  }
  void addEdge(int u, int v, int cap, int f) {
    es.push_back(Edge(v, h[u], cap, f));
    h[u] = (signed)es.size() - 1;
  }
  void addArc(int u, int v, int cap) {
    addEdge(u, v, cap, 0);
    addEdge(v, u, cap, cap);
  }
  Edge& operator[](int p) { return es[p]; }
  void clear() {
    delete[] h;
    es.clear();
  }
} MapManager;
const int N = 605;
int n, m, K;
int s = 0, t;
int mxcap;
int deg[N];
MapManager g;
inline void init() {
  scanf("%d%d%d", &n, &m, &K);
  pfill(deg, deg + n + 1, 0);
  g = MapManager(n + m + 1);
  for (int i = 1, u, v; i <= m; i++) {
    scanf("%d%d", &u, &v);
    deg[u]++, deg[v]++;
    g.addArc(0, i, 1);
    g.addArc(i, u + m, 1);
    g.addArc(i, v + m, 1);
  }
  t = n + m + 1, mxcap = 0;
  for (int i = 1; i <= n; i++)
    if (deg[i] > K) g.addArc(i + m, t, (deg[i] - K) << 1), mxcap += deg[i] - K;
  mxcap <<= 1;
}
int cur[N << 1], _div[N << 1];
int dfs(int p, int mf) {
  if (p == t || !mf) return mf;
  int f, flow = 0;
  for (int &i = cur[p], e; ~i; i = g[i].nx) {
    e = g[i].ed;
    if (g[i].f < g[i].cap && _div[e] == _div[p] + 1 &&
        (f = dfs(e, min(mf, g[i].cap - g[i].f))) > 0) {
      g[i].f += f;
      g[i ^ 1].f -= f;
      mf -= f;
      flow += f;
      if (!mf) break;
    }
  }
  return flow;
}
queue<int> que;
bool bfs() {
  pfill(_div, _div + t + 1, -1);
  _div[s] = 0;
  que.push(s);
  while (!que.empty()) {
    int e = que.front();
    que.pop();
    for (int i = g.h[e], eu; ~i; i = g[i].nx) {
      eu = g[i].ed;
      if (g[i].cap == g[i].f) continue;
      if (~_div[eu]) continue;
      _div[eu] = _div[e] + 1;
      que.push(eu);
    }
  }
  return _div[t] != -1;
}
int dinic() {
  int rt = 0;
  while (bfs()) {
    pcopy(cur, cur + t + 1, g.h);
    rt += dfs(s, inf);
  }
  return rt;
}
int lab[N];
vector<int> mat[N];
inline void solve() {
  int flow = dinic(), used = 0;
  if (flow != mxcap) {
    for (int i = 1; i <= m; i++) printf("0 ");
    putchar('\n');
    return;
  }
  for (int i = 1; i <= n; i++) mat[i].clear();
  for (int i = 1; i <= m; i++)
    for (int j = g.h[i]; ~j; j = g[j].nx)
      if (g[j].cap == g[j].f && g[j].ed > m) {
        mat[g[j].ed - m].push_back(i);
        break;
      }
  pfill(lab + 1, lab + m + 1, 0);
  for (int i = 1, a, b; i <= n; i++)
    while (!mat[i].empty()) {
      a = mat[i].back();
      mat[i].pop_back();
      b = mat[i].back();
      mat[i].pop_back();
      lab[a] = lab[b] = ++used;
    }
  for (int i = 1; i <= m; i++) {
    if (!lab[i]) lab[i] = ++used;
    printf("%d ", lab[i]);
  }
  putchar('\n');
}
inline void clear() { g.clear(); }
int T;
int main() {
  scanf("%d", &T);
  while (T--) {
    init();
    solve();
    clear();
  }
  return 0;
}
