#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
const int MOD = 998244353;

int n, m;
vector<int>v[N];
int ans[N];
int ind[N];

void solve() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) ans[i] = 0;
	for (int i = 1; i <= n; i++) v[i].clear(), ind[i] = 0;
	for (int i = 1; i <= m; i++)
	{
		int x, y;
		cin >> x >> y;
		v[x].push_back(i);
		v[y].push_back(i);
		ind[x]++, ind[y]++;
	}
	if (n == 3)
	{
		cout << m << "\n";
		for (int j = 1; j <= m; j++) cout << j << " ";
		cout << "\n";
		return;
	}
	if (m == n * (n - 1) / 2)
	{
		ans[v[1][0]] = 1;
		for (int i = 1; i < v[1].size(); i++)
			ans[i] = 2;
		cout << "3\n";
		for (int i = 1; i <= m; i++)
		{
			if (!ans[i]) ans[i] = 3;
			cout << ans[i] << " ";
		}
		cout << "\n";
		return;
	}
	cout << "2\n";
	int minn = 1;
	for (int i = 1; i <= n; i++)
		if (ind[i] < ind[minn]) minn = i;
	for (auto y : v[minn]) ans[y] = 1;
	for (int i = 1; i <= m; i++)
	{
		if (!ans[i]) ans[i] = 2;
		cout << ans[i] << " ";
	}
	cout << "\n";
}

int main() 
{
	int tt = 1;
	cin >> tt;
	while (tt--)
		solve();
	system("pause");
	return 0;
}