#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1205;
const int MAXM = 5005;
const int INF = 0x3f3f3f3f;
struct Edge {
  int to, next, cap, flow;
} edge[MAXM];
int tot, head[MAXN];
int Q[MAXN], cur[MAXN], dep[MAXN];
int n, m, S, T, N, to[MAXN];
void init() {
  tot = 2;
  memset(head, -1, sizeof head);
}
void addedge(int u, int v, int w, int rw = 0) {
  edge[tot].to = v;
  edge[tot].cap = w;
  edge[tot].flow = 0;
  edge[tot].next = head[u];
  head[u] = tot++;
  edge[tot].to = u;
  edge[tot].cap = rw;
  edge[tot].flow = 0;
  edge[tot].next = head[v];
  head[v] = tot++;
}
bool bfs(int s, int t, int n) {
  int Front = 0, tail = 0;
  memset(dep, -1, sizeof(dep[0]) * (n + 1));
  dep[s] = 0;
  Q[tail++] = s;
  while (Front < tail) {
    int u = Q[Front++];
    for (int i = head[u]; i != -1; i = edge[i].next) {
      int v = edge[i].to;
      if (edge[i].cap > edge[i].flow && dep[v] == -1) {
        dep[v] = dep[u] + 1;
        if (v == t) return true;
        Q[tail++] = v;
      }
    }
  }
  return false;
}
int dfs(int u, int f) {
  if (u == T) return f;
  int used = 0, rflow = 0;
  for (int i = cur[u]; i != -1; i = edge[i].next) {
    cur[u] = i;
    int v = edge[i].to, w = edge[i].cap - edge[i].flow;
    if (w > 0 && dep[v] == dep[u] + 1) {
      if ((rflow = dfs(v, min(w, f - used)))) {
        used += rflow;
        edge[i].flow += rflow;
        edge[i ^ 1].flow -= rflow;
        if (used == f) break;
      }
    }
  }
  if (!used) dep[u] = -1;
  return used;
}
int dinic(int s, int t, int n) {
  int maxflow = 0;
  while (bfs(s, t, n)) {
    for (int i = 0; i <= n; i++) cur[i] = head[i];
    maxflow += dfs(s, INF);
  }
  return maxflow;
}
int col[MAXN], d[MAXN], k;
int main() {
  ios::sync_with_stdio(false);
  int kase;
  cin >> kase;
  while (kase--) {
    cin >> n >> m >> k;
    init();
    S = 0, T = n + m + 1, N = n + m + 1;
    for (int i = 0; i <= max(n, m); i++) d[i] = 0, col[i] = 0;
    for (int i = 1; i <= m; i++) {
      int a, b;
      cin >> a >> b;
      d[a]++, d[b]++;
      addedge(a, n + i, 1);
      addedge(b, n + i, 1);
      addedge(n + i, T, 1);
    }
    int sum = 0;
    for (int i = 1; i <= n; i++) {
      if (d[i] > k) {
        addedge(S, i, 2 * (d[i] - k));
        sum += 2 * (d[i] - k);
      }
    }
    if (sum == dinic(S, T, N)) {
      int now = 0;
      vector<int> tp;
      for (int i = 1; i <= n; i++) {
        for (int k = head[i]; k != -1; k = edge[k].next) {
          if (edge[k].flow == 1) tp.push_back(edge[k].to);
        }
      }
      for (int i = 0; i < (int)tp.size(); i += 2) {
        col[tp[i] - n] = col[tp[i + 1] - n] = ++now;
      }
      for (int i = 1; i <= m; i++)
        if (col[i] == 0) col[i] = ++now;
    }
    for (int i = 1; i <= m; i++) cout << col[i] << " \n"[i == m];
  }
  return 0;
}
