#include <bits/stdc++.h>
const int MAXN = 1200 + 10;
namespace flow {
const int MAXM = 20000 + 10;
const int MAXN = 2400 + 10;
const int INF = 0x3f3f3f3f;
struct Edge {
  int v, cap, next;
} edge[MAXM << 1];
int head[MAXN], tail = 1;
int insert(int u, int v, int cap) {
  edge[++tail] = (Edge){v, cap, head[u]};
  head[u] = tail;
  edge[++tail] = (Edge){u, 0, head[v]};
  head[v] = tail;
  return tail - 1;
}
void init() {
  memset(head, 0, sizeof head);
  tail = 1;
}
int dis[MAXN];
int cur[MAXN];
int s, t, n;
bool bfs() {
  std::queue<int> q;
  std::fill(dis + 1, dis + n + 1, INF);
  dis[s] = 0;
  q.push(s);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = head[u]; i; i = edge[i].next) {
      int v = edge[i].v;
      if (edge[i].cap && dis[v] == INF) {
        dis[v] = dis[u] + 1;
        q.push(v);
      }
    }
  }
  return dis[t] != INF;
}
int dfs(int u, int a) {
  if (u == t || a == 0) return a;
  int flow = 0, f;
  for (int &i = cur[u]; i; i = edge[i].next) {
    int v = edge[i].v;
    if (dis[u] + 1 == dis[v] && (f = dfs(v, std::min(edge[i].cap, a))) > 0) {
      edge[i].cap -= f;
      edge[i ^ 1].cap += f;
      flow += f;
      a -= f;
      if (a == 0) break;
    }
  }
  return flow;
}
int main(int _s, int _t, int _n) {
  s = _s, t = _t, n = _n;
  int ans = 0;
  while (bfs()) {
    std::copy(head + 1, head + n + 1, cur + 1);
    ans += dfs(s, INF);
  }
  return ans;
}
}  // namespace flow
int n, m, k;
std::vector<std::pair<int, int> > edge;
void fail() {
  for (int i = 1; i <= m; i++) {
    printf("0 ");
  }
  printf("\n");
}
void solve() {
  flow::init();
  static int deg[MAXN];
  memset(deg, 0, sizeof deg);
  edge.clear();
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 1; i <= m; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    edge.emplace_back(a, b);
    deg[a]++;
    deg[b]++;
  }
  for (int i = 1; i <= n; i++) {
    if (2 * k < deg[i]) {
      fail();
      return;
    }
  }
  int s = n + m + 1, t = n + m + 2;
  static int ue[MAXN], ve[MAXN];
  for (int i = 1; i <= m; i++) {
    flow::insert(s, i, 1);
    ue[i] = flow::insert(i, edge[i - 1].first + m, 1);
    ve[i] = flow::insert(i, edge[i - 1].second + m, 1);
  }
  int res = 0;
  for (int i = 1; i <= n; i++) {
    flow::insert(i + m, t, 2 * std::max(deg[i] - k, 0));
    res += 2 * std::max(deg[i] - k, 0);
  }
  if (flow::main(s, t, t) != res) {
    fail();
    return;
  }
  static std::vector<int> gg[MAXN];
  for (int i = 1; i <= n; i++) gg[i].clear();
  static int ans[MAXN];
  int cnt = 0;
  for (int i = 1; i <= m; i++) {
    if (flow::edge[ue[i]].cap == 0)
      gg[edge[i - 1].first].push_back(i);
    else if (flow::edge[ve[i]].cap == 0)
      gg[edge[i - 1].second].push_back(i);
    else
      ans[i] = ++cnt;
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < (int)gg[i].size(); j += 2) {
      ans[gg[i][j]] = ans[gg[i][j + 1]] = ++cnt;
    }
  }
  for (int i = 1; i <= m; i++) {
    printf("%d ", ans[i]);
  }
  printf("\n");
}
int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    solve();
  }
}
