#include<bits/stdc++.h>
using namespace std;
const int N=501000;
int n,m;
struct node{
	int x,y;
}edge[N];
int deg[N];
int main()
{
	int T;cin>>T;
	while(T--)
	{
		cin>>n>>m;
		for(int i=1;i<=n;i++)deg[i]--;
		for(int i=1,x,y;i<=m;i++)
			cin>>x>>y,deg[x]++,deg[y]++,edge[i]=(node){x,y};
		if(m==n*(n-1)/2)
		{
			cout<<3<<'\n';
			for(int i=1,x,y;i<=m;i++)
			{
				x=edge[i].x;y=edge[i].y;
				if(x>y)swap(x,y);
				if(x==1)cout<<((y==2)?3:1)<<' ';
				else cout<<2<<' ';
			}puts("");
		}
		else
		{
			int u=0;
			cout<<2<<'\n';
			for(int i=1;i<=n;i++)if(deg[i]!=n-1)u=i;
			for(int i=1,x,y;i<=m;i++){
				if(edge[i].x==u||edge[i].y==u)cout<<1<<' ';
				else cout<<2<<' ';
			}puts("");
		}
	}return 0;
}