#include <bits/stdc++.h>
using namespace std;
using namespace chrono;
const int N = 1205;
const int INF = 0x3f3f3f3f;
template <class T>
bool read(T& x) {
  char c;
  while (!isdigit(c = getchar()) && c != '-' && c != EOF)
    ;
  if (c == EOF) return false;
  T flag = 1;
  if (c == '-') {
    flag = -1;
    x = 0;
  } else
    x = c - '0';
  while (isdigit(c = getchar())) x = x * 10 + c - '0';
  x *= flag;
  return true;
}
template <class T, class... R>
bool read(T& a, R&... b) {
  if (!read(a)) return false;
  return read(b...);
}
mt19937 gen(steady_clock::now().time_since_epoch().count());
struct edge {
  int to, cap, next;
} e[N * 4];
int head[N], cnt, depth[N], group[N];
void add(int u, int v, int c) {
  e[cnt] = {v, c, head[u]};
  head[u] = cnt++;
}
void add_edge(int u, int v, int c) {
  add(u, v, c);
  add(v, u, 0);
}
bool isap_bfs(int s, int t) {
  memset(depth, -1, sizeof(depth));
  memset(group, 0, sizeof(group));
  group[depth[t] = 0]++;
  queue<int> q;
  q.push(t);
  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 (~depth[v]) continue;
      group[depth[v] = depth[u] + 1]++;
      q.push(v);
    }
  }
  return ~depth[s];
}
int isap_dfs(int u, int t, int c) {
  if (u == t) return c;
  int tmp = c;
  for (int i = head[u]; tmp && ~i; i = e[i].next) {
    int v = e[i].to;
    if (depth[v] + 1 == depth[u] && e[i].cap) {
      int d = isap_dfs(v, t, min(tmp, e[i].cap));
      e[i].cap -= d;
      e[i ^ 1].cap += d;
      tmp -= d;
    }
  }
  if (tmp) {
    if (!--group[depth[u]]) depth[t] = -1;
    group[++depth[u]]++;
  }
  return c - tmp;
}
int isap(int s, int t) {
  if (!isap_bfs(s, t)) return 0;
  int max_flow = 0;
  while (~depth[t]) max_flow += isap_dfs(s, t, INF);
  return max_flow;
}
int deg[N], x[N], y[N], xe[N], ye[N];
vector<int> edg[N];
int main() {
  time_point<steady_clock> start = steady_clock::now();
  int T, n, m, k;
  read(T);
  while (T--) {
    read(n, m, k);
    int s = 0, t = n + m + 1;
    cnt = 0;
    for (int i = s; i <= t; i++) {
      head[i] = -1;
      deg[i] = 0;
      edg[i].clear();
    }
    for (int i = 1; i <= m; i++) {
      read(x[i], y[i]);
      deg[x[i]]++;
      deg[y[i]]++;
      edg[x[i]].push_back(i);
      edg[y[i]].push_back(i);
    }
    for (int i = 1; i <= n; i++) {
      if (deg[i] > 2 * k) {
        k = -1;
        break;
      }
    }
    if (k == -1) {
      for (int i = 1; i <= m; i++) printf("0 ");
      puts("");
      continue;
    }
    int tot = 0;
    for (int i = 1; i <= n; i++) {
      if (deg[i] > k) {
        tot += deg[i] - k;
        add_edge(m + i, t, 2 * (deg[i] - k));
      }
    }
    tot *= 2;
    for (int i = 1; i <= m; i++) {
      add_edge(s, i, 1);
      add_edge(i, m + x[i], 1);
      xe[i] = cnt - 1;
      add_edge(i, m + y[i], 1);
      ye[i] = cnt - 1;
    }
    if (isap(s, t) == tot) {
      for (int i = 1; i <= m; i++) deg[i] = 0;
      k = 1;
      for (int i = 1; i <= n; i++) {
        int c = 0;
        for (auto j : edg[i]) {
          if (x[j] == i && e[xe[j]].cap || y[j] == i && e[ye[j]].cap) {
            if (c == 0)
              deg[j] = k;
            else
              deg[j] = k++;
            c ^= 1;
          }
        }
      }
      for (int i = 1; i <= m; i++)
        if (!deg[i]) deg[i] = k++;
      for (int i = 1; i <= m; i++) printf("%d ", deg[i]);
      puts("");
    } else {
      for (int i = 1; i <= m; i++) printf("0 ");
      puts("");
    }
  }
  cerr << endl
       << "------------------------------" << endl
       << "Time: "
       << duration<double, milli>(steady_clock::now() - start).count() << " ms."
       << endl;
  return 0;
}
