#include <bits/stdc++.h>
using namespace std;
long long int cons;
inline long long int check(long long int a) {
  if (a >= cons) a %= cons;
  return a;
}
inline long long int check2(long long int a) {
  a %= cons;
  if (a < 0) a += cons;
  return a;
}
inline long long int fast_check(long long int a) {
  if (a >= cons) a -= cons;
  return a;
}
long long int GCD(long long int a, long long int b) {
  while (a && b) {
    a = a % b;
    if (a != 0) b = b % a;
  }
  return a + b;
}
long long int exp(long long int a, long long int n) {
  long long int ans = 1;
  a = check(a);
  while (n) {
    if (n & 1) ans = check(ans * a);
    a = check(a * a);
    n = (n >> 1);
  }
  return ans;
}
void print_pair(pair<int, int> p) {
  cout << p.first << " " << p.second << endl;
}
long long int nc2(long long int a) { return (a * (a - 1)) / 2; }
long long int nc3(long long int a) {
  long long int b = a * (a - 1) * (a - 2);
  return b / 6;
}
const int N = 10000;
const int E = 10000;
int par[N];
int nodes, edges;
int eu[E], ev[E], ef[E], ec[E];
int edgenum[E];
int dist[N], q[N], ed[N];
vector<int> adj[N];
void init(int n) {
  nodes = n;
  edges = 0;
  for (int i = 0; i < nodes; ++i) adj[i].clear();
}
int newedge(int u, int v, int flow, int cap, int edgeno) {
  eu[edges] = u;
  ev[edges] = v;
  ef[edges] = flow;
  ec[edges] = cap;
  edgenum[edges] = edgeno;
  return edges++;
}
void addedge(int u, int v, int cap, int edgeno) {
  int uv = newedge(u, v, 0, cap, edgeno);
  int vu = newedge(v, u, 0, 0, edgeno);
  adj[u].push_back(uv);
  adj[v].push_back(vu);
}
bool bfs(int src, int snk) {
  memset(dist, -1, sizeof(int) * nodes);
  int h = 0, t = 0;
  dist[src] = 0;
  q[t++] = src;
  while (h != t && dist[snk] == -1) {
    int u = q[h++];
    if (h == N) h = 0;
    for (int e : adj[u]) {
      int v = ev[e];
      if (dist[v] < 0 && ef[e] < ec[e]) {
        dist[v] = dist[u] + 1;
        q[t++] = v;
        if (t == N) t = 0;
      }
    }
  }
  return ~dist[snk];
}
bool dfs(int u, int snk, int flow) {
  if (flow <= 0) return 0;
  if (u == snk) return flow;
  for (int& i = ed[u]; i < (int)adj[u].size(); ++i) {
    int e = adj[u][i];
    int v = ev[e];
    if (dist[u] + 1 == dist[v]) {
      int fl = min(flow, ec[e] - ef[e]);
      int df = dfs(v, snk, fl);
      if (df == 0) continue;
      ef[e] += df;
      ef[e ^ 1] -= df;
      return df;
    }
  }
  return 0;
}
int dinic(int src, int snk) {
  int mf = 0;
  while (bfs(src, snk)) {
    memset(ed, 0, sizeof(int) * nodes);
    int df;
    while (df = dfs(src, snk, INT_MAX)) mf += df;
  }
  return mf;
}
vector<pair<pair<int, int>, int>> edges_list;
int ans[610];
int deg[610];
int company = 0;
int usenode[610];
int counnode[610];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cons = 1e9 + 7;
  srand(time(NULL));
  int t;
  cin >> t;
  while (t--) {
    int n, m, k;
    cin >> n >> m >> k;
    int source = 0;
    int sink = n + m + 1;
    init(n + m + 2);
    company = 0;
    edges_list.clear();
    for (int i = 1; i <= n; i++) {
      usenode[i] = 0;
      counnode[i] = 0;
      deg[i] = 0;
    }
    for (int i = 1; i <= m; i++) {
      int first, second;
      cin >> first >> second;
      edges_list.push_back({{first, second}, i});
      ans[i] = 0;
      deg[first]++;
      deg[second]++;
    }
    for (auto itr : edges_list) {
      addedge(itr.first.first, n + itr.second, 1, itr.second);
      addedge(itr.first.second, n + itr.second, 1, itr.second);
    }
    bool flag = true;
    int to_get = 0;
    for (int i = 1; i <= n; i++) {
      if (deg[i] > 2 * k) {
        flag = false;
        break;
      }
      if (k >= deg[i]) continue;
      int cap = 2 * (deg[i] - k);
      to_get += cap;
      addedge(source, i, cap, -1);
    }
    if (!flag) {
      for (int i = 1; i <= m; i++) cout << "0 ";
      cout << "\n";
      continue;
    }
    for (int i = 1; i <= m; i++) addedge(n + i, sink, 1, -1);
    int din_flo = dinic(source, sink);
    if (din_flo < to_get) {
      for (int i = 1; i <= m; i++) cout << "0 ";
      cout << "\n";
      continue;
    } else {
      for (int i = 0; i <= edges; i++) {
        if (eu[i] >= 1 && eu[i] <= n && ev[i] > n && ev[i] <= n + m &&
            ef[i] == 1) {
          if (counnode[eu[i]] % 2 == 0) usenode[eu[i]] = ++company;
          ans[edgenum[i]] = usenode[eu[i]];
          counnode[eu[i]]++;
        }
      }
      for (int i = 1; i <= m; i++) {
        if (ans[i] == 0) ans[i] = ++company;
        cout << ans[i] << " ";
      }
      cout << "\n";
    }
  }
  return 0;
}
