#include <bits/stdc++.h>
int n, m, u[1 << 11], v[1 << 11], d[1 << 6];
void solve (void)
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) d[i] = 0;
	for (int i = 1; i <= m; i++) scanf("%d%d", &u[i], &v[i]), d[u[i]]++, d[v[i]]++;
	if (m == n * (n - 1) / 2)
	{
		puts("3");
		for (int i = 1; i <= m; i++) printf("%d%c", ((u[i] == 1 or v[i] == 1) | ((u[i] == 2 or v[i] == 2) << 1)) % 3 + 1, " \n"[i == m]);
	}
	else
	{
		puts("2");
		int p = 1; while (d[p] == n - 1) p++;
		for (int i = 1; i <= m; i++) printf("%d%c", (u[i] == p or v[i] == p) + 1, " \n"[i == m]);
	}
}
signed main ()
{
	int T;
	for (scanf("%d", &T); T--; ) solve();
	return 0;
}