#include <bits/stdc++.h>
using namespace std;
int gi() {
	int res = 0, w = 1;
	char ch = getchar();
	while (ch != '-' && !isdigit(ch)) ch = getchar();
	if (ch == '-') w = -1, ch = getchar();
	while (isdigit(ch)) res = res * 10 + ch - '0', ch = getchar();
	return res * w;
}
#define fi first
#define se second
#define pii pair<int, int>
using LL = long long;
using db = double;
const int Mod = 998244353;
const int MAX_N = 5005;
int N, M, eu[MAX_N], ev[MAX_N], deg[MAX_N];
void solve() {
	N = gi(), M = gi();
	for (int i = 1; i <= M; i++)
		eu[i] = gi(), ev[i] = gi(), deg[eu[i]]++, deg[ev[i]]++;
	int rt = 0;
	for (int i = 1; i <= N; i++) 
		if (deg[i] != N - 1) rt = i;
	if (rt) {
		puts("2");
		for (int i = 1; i <= M; i++)
			if (eu[i] == rt || ev[i] == rt) printf("1 ");
			else printf("2 ");
	} else {
		puts("3");
		int cnt = 0;
		for (int i = 1; i <= M; i++)
			if (eu[i] == 1 || ev[i] == 1) {
				cnt++;
				if (cnt == 1) printf("1 ");
				else printf("3 ");
			} else printf("2 ");
	}
	putchar('\n');
}
int main () {
#ifndef ONLINE_JUDGE
    freopen("cpp.in", "r", stdin);
	//freopen("cpp.out", "w", stdout);
#endif
	int T = gi();
	while (T--) {
		solve();
		for (int i = 1; i <= N; i++) deg[i] = 0;
	}
    return 0;
}