#include <bits/stdc++.h>
using namespace std;
const int INF_of_int = 1e9;
const long long INF_of_ll = 1e18;
template <typename T>
void Read(T &x) {
  bool w = 1;
  x = 0;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-') w = 0, c = getchar();
  while (isdigit(c)) {
    x = (x << 1) + (x << 3) + c - '0';
    c = getchar();
  }
  if (!w) x = -x;
}
template <typename T>
void Write(T x) {
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  if (x > 9) Write(x / 10);
  putchar(x % 10 + '0');
}
const int N = 1e5 + 10;
struct Edge {
  int u, v, cap, flow;
};
vector<Edge> E;
vector<int> G[N];
int S, T;
int d[N], vis[N];
void init(int n) {
  E.clear();
  for (int i = 0; i <= n; ++i) G[i].clear();
}
void add(int u, int v, int cap) {
  E.push_back((Edge){u, v, cap, 0});
  E.push_back((Edge){v, u, 0, 0});
  int m = E.size();
  G[u].push_back(m - 2);
  G[v].push_back(m - 1);
}
bool bfs() {
  memset(vis, 0, sizeof(vis));
  memset(d, 0, sizeof(d));
  queue<int> q;
  q.push(S);
  vis[S] = 1;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < (signed)G[u].size(); ++i) {
      Edge e = E[G[u][i]];
      if (!vis[e.v] && e.cap > e.flow) {
        vis[e.v] = 1;
        d[e.v] = d[u] + 1;
        q.push(e.v);
      }
    }
  }
  return vis[T];
}
int dfs(int u, int a) {
  if (u == T || !a) return a;
  int flow = 0;
  for (int i = 0; i < (signed)G[u].size(); ++i) {
    Edge &e = E[G[u][i]];
    if (d[e.v] != d[u] + 1) continue;
    int f = dfs(e.v, min(a, e.cap - e.flow));
    flow += f;
    a -= f;
    e.flow += f;
    E[G[u][i] ^ 1].flow -= f;
    if (!a) break;
  }
  if (!flow) d[u] = 0;
  return flow;
}
int Max_flow() {
  int flow = 0;
  while (bfs()) flow += dfs(S, INF_of_int);
  return flow;
}
int du[N], u[N], v[N], f[N], pre[N], bel[N];
vector<int> pool[N];
void solve() {
  int n, m, k;
  Read(n), Read(m), Read(k);
  for (int i = 1; i <= n; ++i) {
    du[i] = 0;
    pool[i].clear();
  }
  for (int i = 1; i <= m; ++i) {
    Read(u[i]), Read(v[i]);
    ++du[u[i]], ++du[v[i]];
  }
  int cnt = n, sum = 0;
  S = ++cnt, T = ++cnt;
  for (int i = 1; i <= n; ++i) {
    f[i] = 2 * max(du[i] - k, 0);
    add(i, T, f[i]);
    sum += f[i];
  }
  for (int i = 1; i <= m; ++i) {
    int now = ++cnt;
    add(S, now, 1);
    add(now, u[i], 1);
    pre[i] = E.size() - 2;
    add(now, v[i], 1);
  }
  if (sum != Max_flow()) {
    for (int i = 1; i <= m; ++i) printf("0 ");
    putchar('\n');
    init(cnt);
    return;
  }
  for (int i = 1; i <= m; ++i) {
    if (E[pre[i]].cap == E[pre[i]].flow)
      pool[u[i]].push_back(i);
    else
      pool[v[i]].push_back(i);
  }
  sum = 0;
  for (int i = 1; i <= n; ++i)
    for (int j = 0; j < (signed)pool[i].size(); ++j) {
      if (j & 1)
        bel[pool[i][j]] = bel[pool[i][j - 1]];
      else
        bel[pool[i][j]] = ++sum;
    }
  for (int i = 1; i <= m; ++i) {
    Write(bel[i]);
    putchar(' ');
  }
  putchar('\n');
  init(cnt);
}
int main() {
  int T;
  Read(T);
  while (T--) solve();
  return 0;
}
