#include <bits/stdc++.h>
using namespace std;
struct Dinic {
  struct Edge {
    int to, cap, flow, nxt;
  };
  vector<Edge> edges;
  vector<int> graph, at, dist;
  map<pair<int, int>, int> where;
  int src = 0, dest = 1;
  Dinic(int n) : graph(n, -1), dist(n, -1) {}
  bool getTaken(int from, int to) {
    return edges[where[{from, to}]].cap == edges[where[{from, to}]].flow;
  }
  void add_edge(int from, int to, int cap) {
    where[{from, to}] = edges.size();
    edges.push_back(Edge{to, cap, 0, graph[from]});
    graph[from] = edges.size() - 1;
  }
  void AddEdge(int from, int to, int cap) {
    add_edge(from, to, cap);
    add_edge(to, from, 0);
  }
  bool bfs() {
    queue<int> q;
    fill(dist.begin(), dist.end(), -1);
    dist[src] = 0;
    q.push(src);
    while (!q.empty()) {
      int node = q.front();
      q.pop();
      for (int i = graph[node]; i >= 0; i = edges[i].nxt) {
        const auto &e = edges[i];
        if (dist[e.to] == -1 && e.flow < e.cap) {
          dist[e.to] = dist[node] + 1;
          q.push(e.to);
        }
      }
    }
    return dist[dest] != -1;
  }
  int dfs(int node, int flow) {
    if (flow == 0) return 0;
    if (node == dest) return flow;
    while (at[node] != -1) {
      int eid = at[node];
      const auto &e = edges[eid];
      if (dist[e.to] == dist[node] + 1) {
        if (int ret = dfs(e.to, min(flow, e.cap - e.flow))) {
          edges[eid].flow += ret;
          edges[eid ^ 1].flow -= ret;
          return ret;
        }
      }
      at[node] = e.nxt;
    }
    return 0;
  }
  int Compute(int src, int dest) {
    this->src = src;
    this->dest = dest;
    int ret = 0;
    while (bfs()) {
      at = graph;
      while (int flow = dfs(src, 2e9)) ret += flow;
    }
    return ret;
  }
};
vector<int> graph[1000];
vector<pair<int, int>> edges;
vector<int> needed(1000);
vector<int> colors(1000);
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t;
  cin >> t;
  while (t--) {
    int n, m, k, sumOfNeeded = 0;
    cin >> n >> m >> k;
    int source = 0;
    int destination = n + m + 1;
    Dinic *myFlow = new Dinic(n + m + 2);
    for (int i = 1; i <= n; ++i) {
      graph[i].clear();
      needed[i] = 0;
    }
    for (int i = 0; i < m; ++i) colors[i] = 0;
    edges.clear();
    for (int i = 0; i < m; ++i) {
      int x, y;
      cin >> x >> y;
      edges.push_back({x, y});
      graph[x].push_back(i);
      graph[y].push_back(i);
    }
    for (int i = 1; i <= n; ++i) {
      needed[i] = max(0, (int)graph[i].size() - k);
      needed[i] <<= 1;
      sumOfNeeded += needed[i];
      myFlow->AddEdge(source, i, needed[i]);
      for (auto x : graph[i]) {
        myFlow->AddEdge(i, n + x + 1, 1);
      }
    }
    for (int i = 1; i <= m; ++i) {
      myFlow->AddEdge(n + i, destination, 1);
    }
    int maximumFlow = myFlow->Compute(source, destination);
    if (maximumFlow == sumOfNeeded) {
      int currentColor = 1;
      int used = 0;
      for (int i = 1; i <= n; ++i) {
        for (auto x : graph[i]) {
          if (myFlow->getTaken(i, n + x + 1)) {
            colors[x] = currentColor;
            used += 1;
            if (used == 2) {
              currentColor += 1;
              used = 0;
            }
          }
        }
      }
      used = 0;
      currentColor += 1;
      for (int i = 0; i < m; ++i) {
        if (colors[i]) continue;
        colors[i] = currentColor;
        currentColor += 1;
      }
    }
    for (int i = 0; i < m; ++i) {
      cout << colors[i] << ' ';
    }
    cout << '\n';
  }
}
