#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int inf = 0x3f3f3f3f;
int head[maxn];
struct node {
  int u, v, cap, nt;
  node() {}
  node(int u, int v, int cap, int nt) : u(u), v(v), cap(cap), nt(nt) {}
} edge[maxn];
int cnt;
void addedge(int u, int v, int cap) {
  edge[cnt] = node(u, v, cap, head[u]);
  head[u] = cnt++;
  edge[cnt] = node(v, u, 0, head[v]);
  head[v] = cnt++;
}
int dis[maxn];
int cur[maxn];
bool bfs(int s, int t) {
  memset(dis, -1, sizeof dis);
  queue<int> q;
  dis[s] = 0;
  q.push(s);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = head[u]; ~i; i = edge[i].nt) {
      node no = edge[i];
      int v = no.v;
      int cap = no.cap;
      if (cap > 0 && dis[v] == -1) {
        dis[v] = dis[u] + 1;
        q.push(v);
      }
    }
  }
  return dis[t] != -1;
}
int dfs(int u, int mx, int t) {
  if (u == t) return mx;
  int used = 0;
  for (int i = cur[u]; ~i; i = edge[i].nt) {
    cur[u] = i;
    node &no = edge[i];
    int v = no.v;
    int cap = no.cap;
    if (dis[v] == dis[u] + 1 && cap > 0) {
      int w = mx - used;
      int flow = dfs(v, min(w, cap), t);
      edge[i].cap -= flow;
      edge[i ^ 1].cap += flow;
      used += flow;
      if (used == mx) return used;
    }
  }
  if (!used) dis[u] = -1;
  return used;
}
int dinic(int s, int t, int tot) {
  int ans = 0;
  while (bfs(s, t)) {
    int flow;
    for (int i = 0; i < tot; i++) cur[i] = head[i];
    while (flow = dfs(s, inf, t)) ans += flow;
  }
  return ans;
}
int deg[maxn];
int id[maxn][2];
int an[maxn], u[maxn], v[maxn];
vector<int> t[maxn];
int main() {
  int T;
  scanf("%d", &T);
  for (; T--;) {
    int n, m, k;
    scanf("%d", &n), scanf("%d", &m), scanf("%d", &k);
    for (int i = 0; i <= n + m + 2; ++i) head[i] = -1, deg[i] = 0;
    cnt = 0;
    for (int i = 1; i <= m; ++i) {
      scanf("%d", &u[i]), scanf("%d", &v[i]);
      ++deg[u[i]], ++deg[v[i]];
      addedge(0, n + i, 1);
      addedge(n + i, u[i], 1);
      id[i][0] = cnt - 1;
      addedge(n + i, v[i], 1);
      id[i][1] = cnt - 1;
    }
    int tot = 0;
    for (int i = 1; i <= n; ++i) {
      int x = deg[i] - k;
      if (x <= 0) continue;
      x *= 2;
      tot += x;
      addedge(i, n + m + 1, x);
    }
    int ans = dinic(0, n + m + 1, n + m + 2);
    if (ans == tot) {
      for (int i = 1; i <= m; i++) {
        int tt = id[i][0];
        if (edge[tt].cap == 1) {
          t[u[i]].push_back(i);
          continue;
        }
        tt = id[i][1];
        if (edge[tt].cap == 1) {
          t[v[i]].push_back(i);
          continue;
        }
        an[i] = i;
      }
      int k = m;
      for (int i = 1; i <= n; i++) {
        int sz = t[i].size();
        for (int j = 0; j < sz; j += 2) {
          ++k;
          an[t[i][j]] = k;
          an[t[i][j + 1]] = k;
        }
        t[i].clear();
      }
      for (int i = 1; i <= m; ++i) printf("%d%c", an[i], " \n"[i == m]);
    } else {
      for (int i = 1; i <= m; ++i) printf("0%c", " \n"[i == m]);
    }
  }
  return 0;
}
