#include <bits/stdc++.h>
using namespace std;
const int maxn = 1200 + 5;
const long long inf = 1e9 + 7;
long long n, m, k;
struct edge {
  int from, to;
  long long flow;
  edge() {}
  edge(int from, int to, long long flow) {
    this->from = from;
    this->to = to;
    this->flow = flow;
  }
};
vector<int> g[maxn];
vector<edge> e;
int dis[maxn];
bool vis[maxn];
long long ans = 0;
int startPoint, endPoint;
int d[maxn];
int tot = 1;
vector<int> son[maxn];
int Son = 0;
int too[maxn];
vector<int> s[maxn];
inline void add(int a, int b, long long c) {
  e.push_back(edge(a, b, c));
  e.push_back(edge(b, a, 0));
  int len = e.size();
  if (a >= 1 && a <= m && b >= m + 1 && b < endPoint) s[b].push_back(len - 2);
  g[a].push_back(len - 2);
  g[b].push_back(len - 1);
  return;
}
bool bfs() {
  memset(dis, -1, sizeof(dis));
  queue<int> que;
  dis[startPoint] = 0;
  que.push(startPoint);
  bool flag = 0;
  while (!que.empty()) {
    int x = que.front();
    que.pop();
    int len = g[x].size();
    for (int i = 0; i < len; i++) {
      int toNum = g[x][i];
      int to = e[g[x][i]].to;
      long long flow = e[toNum].flow;
      if (flow > 0 && dis[to] == -1) {
        dis[to] = dis[x] + 1;
        que.push(to);
        if (to == endPoint) flag = 1;
      }
    }
  }
  return flag;
}
long long dfs(int x, long long flow) {
  if (x == endPoint || flow == 0) return flow;
  long long res = 0, f;
  int len = g[x].size();
  for (int i = 0; i < len; i++) {
    int toNum = g[x][i];
    int to = e[toNum].to;
    long long c = e[toNum].flow;
    if (dis[to] == dis[x] + 1 && c > 0) {
      f = dfs(to, min(flow, c));
      if (f <= 0) continue;
      e[toNum].flow -= f;
      e[toNum ^ 1].flow += f;
      res += f;
      flow -= f;
      if (flow == 0) break;
    }
  }
  return res;
}
void maxflow() {
  ans = 0;
  while (bfs()) ans += dfs(startPoint, inf);
}
inline void init() {
  for (int i = 0; i <= endPoint; i++) {
    s[i].clear();
    g[i].clear();
    son[i].clear();
    d[i] = 0;
    too[i] = 0;
  }
  e.clear();
  tot = 1;
}
int main() {
  int T;
  cin >> T;
  while (T--) {
    scanf("%I64d%I64d%I64d", &n, &m, &k);
    startPoint = 0, endPoint = m + n + 1;
    init();
    for (int i = 1; i <= m; i++) {
      add(startPoint, i, 1);
    }
    for (int i = 1; i <= m; i++) {
      int x, y;
      scanf("%d%d", &x, &y);
      add(i, x + m, 1);
      add(i, y + m, 1);
      d[x]++;
      d[y]++;
    }
    long long sum = 0;
    for (int i = 1; i <= n; i++)
      add(m + i, endPoint, max(0LL, 2LL * (d[i] - k))),
          sum += max(2LL * (d[i] - k), 0LL);
    maxflow();
    if (ans == sum) {
      for (int i = m + 1; i < endPoint; i++) {
        for (int j = 0; j < s[i].size(); j++) {
          int to = s[i][j];
          if (e[to].flow == 0) son[i].push_back(e[to].from);
        }
      }
      for (int i = m + 1; i < endPoint; i++) {
        if (son[i].size() == 0)
          continue;
        else {
          int len = son[i].size();
          for (int j = 0; j < len; j += 2) {
            too[son[i][j]] = too[son[i][j + 1]] = tot++;
          }
        }
      }
      for (int i = 1; i <= m; i++) {
        if (!too[i]) {
          too[i] = tot++;
        }
      }
      for (int i = 1; i <= m; i++) printf("%d ", too[i]);
    } else {
      for (int i = 1; i <= m; i++) {
        printf("0 ");
      }
    }
    puts("");
  }
  return 0;
}
