#include <bits/stdc++.h>
using namespace std;
struct ekedge {
  int flow, cap, from, to, revid;
  ekedge(int flow, int cap, int from, int to, int revid)
      : flow(flow), cap(cap), from(from), to(to), revid(revid) {}
};
struct EdmondsKarp {
  vector<ekedge*> edgelist;
  vector<vector<ekedge*> > adj;
  vector<ekedge*> par;
  queue<ekedge*> q;
  int source;
  int sink;
  int INFI = 2000000000;
  bool calledMaxFlow = false;
  int nodeNumber;
  EdmondsKarp(int nodeNumber, int source, int sink) {
    if (nodeNumber >= 1000000000) {
      cout << "WARNING: flow graph node count is very large; this will "
              "segmentation fault"
           << endl;
    }
    this->source = source;
    this->sink = sink;
    this->nodeNumber = nodeNumber;
    par.resize(nodeNumber);
    adj.resize(nodeNumber);
  }
  void add_edge(int cap, int from, int to) {
    if (from >= nodeNumber || to >= nodeNumber)
      cout << "Warning: Edge from " << from << " to " << to << " with capacity"
           << cap << "is out of bounds." << endl;
    ekedge* v = new ekedge(0, cap, from, to, edgelist.size() + 1);
    ekedge* v_rev = new ekedge(0, 0, to, from, edgelist.size());
    edgelist.push_back(v);
    edgelist.push_back(v_rev);
    adj[from].push_back(v);
    adj[to].push_back(v_rev);
  }
  bool find_aug_path() {
    for (int i = 0; i < par.size(); i++) par[i] = NULL;
    while (!q.empty()) q.pop();
    q.push(new ekedge(0, 0, source, source, -1));
    while (!q.empty()) {
      ekedge* curedge = q.front();
      int curnode = curedge->to;
      q.pop();
      if (curnode == sink) return true;
      for (int i = 0; i < adj[curnode].size(); i++) {
        if (par[adj[curnode][i]->to] == NULL &&
            adj[curnode][i]->cap - adj[curnode][i]->flow > 0) {
          par[adj[curnode][i]->to] = adj[curnode][i];
          q.push(adj[curnode][i]);
        }
      }
    }
    return false;
  }
  long long get_max_flow() {
    for (int i = 0; i < edgelist.size(); i++) edgelist[i]->flow = 0;
    calledMaxFlow = true;
    long long maxflow = 0;
    while (find_aug_path()) {
      int curnode = sink;
      int augment_flow = INFI;
      while (curnode != source) {
        ekedge* curpar = par[curnode];
        augment_flow = min(augment_flow, curpar->cap - curpar->flow);
        curnode = curpar->from;
      }
      curnode = sink;
      while (curnode != source) {
        ekedge* curpar = par[curnode];
        curpar->flow += augment_flow;
        edgelist[curpar->revid]->flow -= augment_flow;
        curnode = curpar->from;
      }
      maxflow += augment_flow;
    }
    return maxflow;
  }
  vector<int> get_flow_values() {
    vector<int> flow_values;
    if (calledMaxFlow) {
      for (int i = 0; i < edgelist.size(); i += 2) {
        flow_values.push_back(edgelist[i]->flow);
      }
    } else {
      cout << "Error: cannot get flow values since get_max_flow has not been "
              "called"
           << endl;
    }
    return flow_values;
  }
  vector<ekedge*> get_edges() {
    vector<ekedge*> edges;
    for (int i = 0; i < edgelist.size(); i += 2) {
      edges.push_back(edgelist[i]);
    }
    return edges;
  }
};
vector<pair<int, int> > adj[601];
int INF = 1000000;
vector<int> assign[601];
int ans[601];
int n, m, k;
int main() {
  int t;
  cin >> t;
  while (t--) {
    bool pos = true;
    long long totmatch = 0;
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
      adj[i].clear();
      assign[i].clear();
    }
    for (int i = 1; i <= m; i++) ans[i] = 0;
    for (int i = 0; i < m; i++) {
      int a, b;
      cin >> a >> b;
      adj[a].emplace_back(i, b);
      adj[b].emplace_back(i, a);
    }
    EdmondsKarp* ek = new EdmondsKarp(n + m + 2, 0, 1);
    for (int i = 1; i <= n; i++) {
      if (adj[i].size() > 2 * k) pos = false;
      ek->add_edge(2 * max((int)adj[i].size() - k, 0), 0, 1 + i);
      totmatch += 2 * max((int)adj[i].size() - k, 0);
      for (int j = 0; j < adj[i].size(); j++)
        ek->add_edge(INF, 1 + i, 2 + n + adj[i][j].first);
    }
    for (int i = 0; i < m; i++) {
      ek->add_edge(1, 2 + n + i, 1);
    }
    if (ek->get_max_flow() == totmatch && pos) {
      vector<ekedge*> edges = ek->get_edges();
      for (int i = 0; i < edges.size(); i++) {
        if (edges[i]->from != 0 && edges[i]->to != 1 && edges[i]->flow != 0)
          assign[edges[i]->from - 2].push_back(edges[i]->to - n - 1);
      }
      int compcnt = 1;
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < assign[i].size(); j += 2) {
          ans[assign[i][j]] = compcnt;
          ans[assign[i][j + 1]] = compcnt++;
        }
      }
      for (int i = 1; i <= m; i++) {
        if (ans[i] != 0)
          cout << ans[i] << ' ';
        else
          cout << compcnt++ << ' ';
      }
      cout << '\n';
    } else {
      for (int i = 0; i < m; i++) cout << 0 << ' ';
      cout << '\n';
    }
  }
}
