#include <bits/stdc++.h>
using namespace std;
const int N = 610;
const int INF = 0x3f3f3f3f;
int head[N << 2], cnt, dis[N << 2], s, t, cur[N << 2], in[N << 2], id[N << 2],
    col[N << 2], tot;
vector<int> G[N << 2];
struct edge {
  int next, to, w;
} e[N * N];
void add(int u, int v, int w) {
  e[++cnt].next = head[u];
  e[cnt].to = v;
  e[cnt].w = w;
  head[u] = cnt;
}
void add_edge(int u, int v, int w) {
  add(u, v, w);
  add(v, u, 0);
}
bool bfs(int s) {
  for (int i = 1; i <= t; i++) dis[i] = -1;
  dis[s] = 0;
  queue<int> q;
  q.push(s);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = head[u]; i; i = e[i].next) {
      int v = e[i].to;
      if (e[i].w && dis[v] == -1) {
        dis[v] = dis[u] + 1;
        q.push(v);
        if (v == t) return true;
      }
    }
  }
  return false;
}
int dfs(int u, int flo) {
  if (u == t) return flo;
  int detla = flo;
  for (int i = cur[u]; i; i = e[i].next) {
    cur[u] = e[i].next;
    int v = e[i].to;
    if (e[i].w && dis[v] == dis[u] + 1) {
      int d = dfs(v, min(detla, e[i].w));
      e[i].w -= d;
      e[i ^ 1].w += d;
      detla -= d;
      if (detla == 0) break;
    }
  }
  return flo - detla;
}
int dini() {
  int ans = 0;
  while (bfs(s)) {
    for (int i = 1; i <= t; i++) cur[i] = head[i];
    ans += dfs(s, INF);
  }
  return ans;
}
void init(int n, int m) {
  cnt = 1;
  tot = 0;
  for (int i = 1; i <= n; i++) in[i] = 0, G[i].clear();
  for (int i = 1; i <= m; i++) id[i] = col[i] = 0;
  for (int i = 1; i <= n + m + 5; i++) head[i] = 0;
}
int main() {
  int T, n, m, k;
  scanf("%d", &T);
  while (T--) {
    scanf("%d %d %d", &n, &m, &k);
    init(n, m);
    t = n + m + 2, s = n + m + 1;
    for (int i = 1; i <= m; i++) {
      int a, b;
      scanf("%d %d", &a, &b);
      in[a]++;
      in[b]++;
      G[a].push_back(i);
      G[b].push_back(i);
      add_edge(a, n + i, 1);
      add_edge(b, n + i, 1);
    }
    int x = cnt;
    int sum = 0;
    for (int i = 1; i <= n; i++)
      if (in[i] > k) add_edge(s, i, 2 * (in[i] - k)), sum += 2 * (in[i] - k);
    for (int i = 1; i <= m; i++) add_edge(n + i, t, 1);
    int ans = dini();
    if (ans == sum) {
      vector<int> R[610];
      for (int i = 2; i <= x; i += 2) {
        if (e[i].w == 0) {
          int v = e[i].to;
          int u = e[i ^ 1].to;
          R[u].push_back(v);
        }
      }
      for (int i = 1; i <= n; i++) {
        int siz = R[i].size();
        for (int j = 0; j < siz; j += 2) {
          col[R[i][j] - n] = col[R[i][j + 1] - n] = ++tot;
        }
      }
      for (int i = 1; i <= m; i++)
        if (!col[i]) col[i] = ++tot;
    }
    for (int i = 1; i <= m; i++) printf("%d%c", col[i], i == m ? '\n' : ' ');
  }
  return 0;
}
