#include <bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("unroll-loops")
using namespace std;
template <class T>
inline T bigmod(T p, T e, T M) {
  long long ret = 1;
  for (; e > 0; e >>= 1) {
    if (e & 1) ret = (ret * p) % M;
    p = (p * p) % M;
  }
  return (T)ret;
}
template <class T>
inline T gcd(T a, T b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
template <class T>
inline T modinverse(T a, T M) {
  return bigmod(a, M - 2, M);
}
template <class T>
inline T lcm(T a, T b) {
  a = abs(a);
  b = abs(b);
  return (a / gcd(a, b)) * b;
}
template <class T, class X>
inline bool getbit(T a, X i) {
  T t = 1;
  return ((a & (t << i)) > 0);
}
template <class T, class X>
inline T setbit(T a, X i) {
  T t = 1;
  return (a | (t << i));
}
template <class T, class X>
inline T resetbit(T a, X i) {
  T t = 1;
  return (a & (~(t << i)));
}
inline long long getnum() {
  char c = getchar();
  long long num, sign = 1;
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') sign = -1;
  for (num = 0; c >= '0' && c <= '9';) {
    c -= '0';
    num = num * 10 + c;
    c = getchar();
  }
  return num * sign;
}
inline long long power(long long a, long long b) {
  long long multiply = 1;
  for (int i = (0); i < (b); i++) {
    multiply *= a;
  }
  return multiply;
}
struct Edge {
  int to, rev, f, cap;
};
class Dinic {
 public:
  int dist[1500], q[1500], work[1500], src, dest;
  vector<Edge> graph[1500];
  void init(int sz) {
    for (int i = (0); i < (sz + 1); i++) graph[i].clear();
  }
  void clearFlow(int sz) {
    for (int i = (0); i < (sz + 1); i++) {
      for (int j = (0); j < (graph[i].size()); j++) graph[i][j].f = 0;
    }
  }
  void addEdge(int s, int t, int cap) {
    Edge a = {t, (int)graph[t].size(), 0, cap};
    Edge b = {s, (int)graph[s].size(), 0, 0};
    graph[s].push_back(a);
    graph[t].push_back(b);
  }
  bool bfs() {
    memset(dist, -1, sizeof(dist));
    dist[src] = 0;
    int qt = 0;
    q[qt++] = src;
    for (int qh = 0; qh < qt; qh++) {
      int u = q[qh];
      for (int j = 0; j < graph[u].size(); j++) {
        Edge &e = graph[u][j];
        int v = e.to;
        if (dist[v] < 0 && e.f < e.cap) {
          dist[v] = dist[u] + 1;
          q[qt++] = v;
        }
      }
    }
    return dist[dest] >= 0;
  }
  int dfs(int u, int f) {
    if (u == dest) return f;
    for (int &i = work[u]; i < (int)graph[u].size(); i++) {
      Edge &e = graph[u][i];
      if (e.cap <= e.f) continue;
      int v = e.to;
      if (dist[v] == dist[u] + 1) {
        int df = dfs(v, min(f, e.cap - e.f));
        if (df > 0) {
          e.f += df;
          graph[v][e.rev].f -= df;
          return df;
        }
      }
    }
    return 0;
  }
  int maxFlow(int _src, int _dest) {
    src = _src;
    dest = _dest;
    int result = 0;
    while (bfs()) {
      fill(work, work + 1500, 0);
      while (int delta = dfs(src, 1e9)) result += delta;
    }
    return result;
  }
} network;
int n, m, k, u[1500], v[1500];
int deg[1500], src, sink, color[1500];
int main() {
  int test, cases = 1;
  scanf("%d", &test);
  while (test--) {
    scanf("%d%d%d", &n, &m, &k);
    network.init(n + m + 5);
    memset(color, 0, sizeof(color));
    memset(deg, 0, sizeof(deg));
    src = 0, sink = n + m + 3;
    for (int i = (1); i < (m + 1); i++) {
      scanf("%d%d", &u[i], &v[i]);
      deg[u[i]]++;
      deg[v[i]]++;
      network.addEdge(u[i], i + n, 1);
      network.addEdge(v[i], i + n, 1);
      network.addEdge(i + n, sink, 1);
    }
    int total = 0;
    for (int i = (1); i < (n + 1); i++) {
      int cap = max(0, 2 * (deg[i] - k));
      network.addEdge(src, i, cap);
      total += cap;
    }
    int flow = network.maxFlow(src, sink);
    if (flow != total) {
      for (int J = 1; J <= m; J++) cout << color[J] << " ";
      cout << "\n";
      ;
    } else {
      int t = 1;
      for (int i = 1; i <= n; i++) {
        vector<int> incident;
        for (auto it : network.graph[i]) {
          if (it.to > n && it.to <= n + m && it.f == 1) {
            incident.push_back(it.to - n);
          }
        }
        for (int i = 0; i < incident.size(); i += 2) {
          color[incident[i]] = color[incident[i + 1]] = t++;
        }
      }
      for (int i = (1); i < (m + 1); i++)
        if (!color[i]) color[i] = t++;
      for (int J = 1; J <= m; J++) cout << color[J] << " ";
      cout << "\n";
      ;
    }
  }
  return 0;
}
