#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 7;
const int N = 1200 + 5;
const int M = 2e5 + 5;
int n, m, s, t, maxflow = 0, lowflow;
struct node {
  int to, w, next, flow;
} edge[M];
int head[N], cnt = 1, dep[N], inque[N], cur[N];
void add(int u, int v, int w) {
  edge[++cnt].next = head[u];
  edge[cnt].to = v;
  edge[cnt].w = w;
  edge[cnt].flow = 0;
  head[u] = cnt;
}
struct Maxflow {
  bool bfs() {
    queue<int> q;
    memset(dep, -1, sizeof dep);
    dep[s] = 0;
    q.push(s);
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      inque[u] = 0;
      for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].to, w = edge[i].w;
        if (dep[v] == -1 && w) {
          dep[v] = dep[u] + 1;
          q.push(v);
        }
      }
    }
    return dep[t] != -1;
  }
  int dfs(int u, int flow) {
    if (u == t) {
      return flow;
    }
    int rlow = 0, used = 0;
    for (int i = cur[u]; i; i = edge[i].next) {
      int v = edge[i].to, w = edge[i].w;
      if (w && dep[v] == dep[u] + 1) {
        if (rlow = dfs(v, min(flow, w))) {
          used += rlow;
          flow -= rlow;
          edge[i].w -= rlow;
          edge[i ^ 1].w += rlow;
          edge[i].flow += rlow;
          edge[i ^ 1].flow -= rlow;
          if (flow == 0) break;
        }
      }
    }
    if (!used) dep[u] = -1;
    return used;
  }
  int Dinic() {
    maxflow = 0;
    while (bfs()) {
      for (int i = 1; i <= t; i++) cur[i] = head[i];
      maxflow += dfs(s, INF);
    }
    return maxflow;
  }
  void init() {
    cnt = 1;
    memset(head, 0, sizeof head);
  }
  void addedge(int u, int v, int w) {
    add(u, v, w);
    add(v, u, 0);
  }
} ac;
int vis[M];
int deg[N];
int k;
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    ac.init();
    scanf("%d%d%d", &n, &m, &k);
    s = n + m + 1, t = n + m + 2;
    for (int i = 1; i <= n; i++) deg[i] = 0;
    for (int i = 1, u, v; i <= m; i++) {
      scanf("%d%d", &u, &v);
      deg[u]++, deg[v]++;
      ac.addedge(u, n + i, 1);
      ac.addedge(v, n + i, 1);
      ac.addedge(n + i, t, 1);
      vis[i] = 0;
    }
    int flag = 0, sum = 0;
    for (int i = 1; i <= n; i++) {
      if (deg[i] > 2 * k)
        flag = 1;
      else if (deg[i] > k) {
        ac.addedge(s, i, 2 * (deg[i] - k));
        sum = sum + 2 * (deg[i] - k);
      }
    }
    if (flag == 1 || ac.Dinic() != sum) {
      for (int i = 1; i <= m; i++) printf("%d ", 0);
      printf("\n");
      continue;
    }
    vector<int> ans;
    for (int u = 1; u <= n; u++) {
      for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].to;
        if (v >= n + 1 && v <= n + m && edge[i].w == 0) ans.push_back(v - n);
      }
    }
    int len = ans.size(), id = 0;
    for (int i = 0; i + 1 < len; i += 2) {
      vis[ans[i]] = vis[ans[i + 1]] = ++id;
    }
    for (int i = 1; i <= m; i++) {
      if (vis[i] == 0) vis[i] = ++id;
      printf("%d ", vis[i]);
    }
    printf("\n");
  }
}
