#include <stdio.h>
#include <cstring>


using namespace std;

#define ll long long
#define PII pair <int, int>
#define fr first
#define sc second
#define mp make_pair

inline int min(int a, int b) { return a < b ? a : b; }
inline int max(int a, int b) { return a > b ? a : b; }
inline int Read() {
	int x = 0; char y; bool z = false;
	do y = getchar(), z |= y == '-'; while (y < '0' || y > '9');
	do x = x * 10 + y - '0', y = getchar(); while (y >= '0' && y <= '9');
	return z ? -x : x;
}

#define N 605 * 2
#define INF 0x7f7f7f7f

int fi[N], c[N * 4][3], ss, d[N];
int n, m, t, p, S = N - 1, T = N - 2, _size;
int ln[N][2];

inline void Line(int x, int y, int z) {
	c[++ss][0] = y; c[ss][1] = fi[x]; fi[x] = ss; c[ss][2] = z;
	c[++ss][0] = x; c[ss][1] = fi[y]; fi[y] = ss; c[ss][2] = 0;
	return;
}

int h[N], li[N];

int BFS()
{
	int le = 1, ri = 1, i;
	memset(h, false, _size); h[S] = h[T] = 0;
	h[S] = 1; li[1] = S;
	for (; le <= ri; le++)
		for (i = fi[li[le]]; i; i = c[i][1])
			if (c[i][2] && !h[c[i][0]])
				h[c[i][0]] = h[li[le]] + 1, li[++ri] = c[i][0];
	return h[T];
}

int DFS(int x, int y)
{
	int i, j = 0, k;
	if (x == T) return y;
	for (i = fi[x]; i&&y; i = c[i][1])
		if (c[i][2] && h[c[i][0]] == h[x] + 1)
		{
			k = DFS(c[i][0], min(y, c[i][2]));
			if (!k) continue;
			y -= k; c[i][2] -= k; j += k; c[i ^ 1][2] += k;
		}
	return j;
}

void Clear() {
	memset(fi, false, _size); ss = 1;
	memset(d, false, _size);
	fi[S] = fi[T] = d[S] = d[T] = 0;
	return;
}

int Ans[N], Now[N];

bool Check() {
	for (int i = 1; i <= n; i++)
		if ((d[i] - p) * 2 > d[i])
			return false; else
			Line(i, T, max((d[i] - p) * 2, 0));
	while (BFS()) DFS(S, INF);
	for (int i = 1; i <= n; i++)
		for (int j = fi[i]; j; j = c[j][1])
			if (c[j][0] == T && c[j][2])
				return false;
	return true;
}

int vis[N];

int main()
{
	freopen("input.dat", "r", stdin);
	freopen("output.sol", "w", stdout);
	t = Read();
	while (t--) {
		n = Read(); m = Read(); p = Read();
		_size = (n + m + 5) * (sizeof(int));
		Clear();
		for (int i = 1; i <= m; i++) {
			int k = Read(), l = Read();
			ln[i][0] = k; ln[i][1] = l;
			Line(S, n + i, 1);
			Line(n + i, k, 1);
			Line(n + i, l, 1);
			d[k]++; d[l]++;
		}
		if (!Check()) {
			for (int i = 1; i <= m; i++)
				Ans[i] = 0;
		}
		else {
			int ri = 0;
			for (int i = 1; i <= n; i++)
				Now[i] = 0;
			bool flag = false;
			for (int i = 1; i <= m; i++)
				for (int j = fi[i + n]; j; j = c[j][1]) {
					if (c[j][0] > n)
						continue;
					if (!c[j][2] || flag) {
						int k = c[j][0];
						if (Now[k])
							Ans[i] = Now[k], Now[k] = 0; else
							Ans[i] = Now[k] = ++ri;
						flag = false;
						break;
					}
					flag = true;
				}
		}
		for (int i = 1; i <= m; i++)
			printf("%d ", Ans[i]);
		puts("");
	}
	return 0;
}