#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 M = 10000;
vector<pair<int, int> > graph[N];
int edge_count = 0;
int visited_from[N];
int edge_entering[N];
int reverse_no[M];
int capacity[M];
int max_flow_dfs[N];
void init(int n) {
  for (int i = 1; i <= n; i++) graph[i].clear();
  edge_count = 0;
}
void addedge(int first, int second, int cap) {
  ++edge_count;
  capacity[edge_count] = cap;
  graph[first].push_back({second, edge_count});
  ++edge_count;
  capacity[edge_count] = 0;
  graph[second].push_back({first, edge_count});
  reverse_no[edge_count] = edge_count - 1;
  reverse_no[edge_count - 1] = edge_count;
}
void dfs(int source) {
  for (auto itr : graph[source]) {
    if (visited_from[itr.first] == -1 && capacity[itr.second]) {
      edge_entering[itr.first] = itr.second;
      visited_from[itr.first] = source;
      max_flow_dfs[itr.first] = min(capacity[itr.second], max_flow_dfs[source]);
      dfs(itr.first);
    }
  }
}
void reverse_edge(int i, int flow) {
  while (visited_from[i] != 0) {
    capacity[edge_entering[i]] -= flow;
    capacity[reverse_no[edge_entering[i]]] += flow;
    i = visited_from[i];
  }
}
int ford_faulkerson(int source, int sink, int n) {
  int ans = 0;
  while (true) {
    for (int i = 1; i <= n; i++) visited_from[i] = -1;
    visited_from[source] = 0;
    max_flow_dfs[source] = 1e9;
    dfs(source);
    if (visited_from[sink] == -1) break;
    ans += max_flow_dfs[sink];
    reverse_edge(sink, max_flow_dfs[sink]);
  }
  return ans;
}
int ans[610];
int deg[610];
int company = 0;
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 = n + m + 1;
    int sink = n + m + 2;
    init(n + m + 2);
    company = 0;
    for (int i = 1; i <= n; i++) deg[i] = 0;
    for (int i = 1; i <= m; i++) {
      int first, second;
      cin >> first >> second;
      ans[i] = 0;
      deg[first]++;
      deg[second]++;
      addedge(first, n + i, 1);
      addedge(second, n + i, 1);
    }
    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);
    }
    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);
    int flow = ford_faulkerson(source, sink, sink);
    if (flow < to_get) {
      for (int i = 1; i <= m; i++) cout << "0 ";
      cout << "\n";
      continue;
    } else {
      for (int i = 1; i <= n; i++) {
        int coun = 0;
        for (auto itr : graph[i]) {
          if (itr.first > n && itr.first <= n + m &&
              capacity[itr.second] == 0) {
            if (!coun) company++;
            ans[itr.first - n] = company;
            coun = 1 - coun;
          }
        }
      }
      for (int i = 1; i <= m; i++) {
        if (ans[i] == 0) ans[i] = ++company;
        cout << ans[i] << " ";
      }
      cout << "\n";
    }
  }
  return 0;
}
