There will be only 3 cases in total
- if the edges are even
- odd edges with atleast one vertex of odd degree
- odd edges with no vertex of odd degree.
in 2nd case just split in 2 parts with dividing the odd degree vertex
in 3rd case divide in 3 parts
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while (t--)
{
int n,m,f=0,val;
cin>>n>>m;
int arr[n+5];
for(int i=0;i<=n;i++){
arr[i]=1;
}
vector<vector<int>>graph(n+5);
vector<pair<int,int>>connect;
for(int i=0;i<m;i++){
int j,k;
cin>>j>>k;
graph[j].push_back(k);
graph[k].push_back(j);
connect.push_back(make_pair(k,j));
}
if(m%2==0){
cout<<"1"<<endl;
for(int i=1;i<=n;i++){
cout<<arr[i]<<" ";
}
cout<<endl;
}
else{
for(auto it=connect.begin();it!=connect.end();it++){
int u=it->first,v=it->second;
if(graph[u].size()%2==1){
val=2;
f=1;
arr[u]=2;
break;
}
else if(graph[v].size()%2==1){
f=1;
arr[v]=2;
val=2;
break;
}
}
if(f!=1){
val=3;
arr[connect.begin()->first]=3;
arr[connect.begin()->second]=2;
}
cout<<val<<endl;
for(int i=1;i<=n;i++)
{
cout<<arr[i]<<" ";
}
cout<<endl;
}
}
return 0;
}