#include <bits/stdc++.h>

using namespace std;


void solve() {
	
	int t;
	cin >> t;
	while(t--){
		int n,m;
		cin >> n >> m;
	
		vector<vector<int> > adj(n+1,vector<int>());
		vector<pair<int,int> > listRoutes(m);
		int a,b;
		for(int i=0;i<m;i++){
			cin >> a >> b;
			listRoutes[i] = {a,b};
			adj[a].push_back(b);
			adj[b].push_back(a);
		}


		int finalNode = -1;
		int minDegree = 1e9;
		int minNode = -1;
		for(int i=1;i<=n;i++){
			if(adj[i].size() == 1){
				finalNode = i;
			}
			if((int)adj[i].size() < minDegree){
				minDegree = adj[i].size();
				minNode = i;
			}
		}

		if(finalNode != -1){
			cout << 2 << endl;
			for(int i=0;i<m;i++){
				if(listRoutes[i].first == finalNode || listRoutes[i].second == finalNode){
					cout << 1 << " ";
				}else{
					cout << 2 << " ";
				}
			}

		}else{
			cout << 3 << endl;
			int cnt = 0;
			for(auto p : listRoutes){
				if(p.first == minNode || p.second == minNode){
					cnt++;
					if(cnt == minDegree){
						cout << 3 << " ";
					}else{
						cout << 1 << " ";
					}
				}else{
					cout << 2 << " ";
				}
			}

		}
		cout << endl;


	}

}

int main() {


	solve();

	ios_base::sync_with_stdio(false);
	cin.tie(0);

	return 0;
}