import java.util.;
import java.lang.;
import java.io.*;
public class Main
{
public static void main(String[] args) throws java.lang.Exception {
BufferedReader br = new BufferedReader(
new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int t= Integer.parseInt(st.nextToken());
while(t–!=0){
st = new StringTokenizer(br.readLine());
int n= Integer.parseInt(st.nextToken());
int m= Integer.parseInt(st.nextToken());
ArrayList<ArrayList<Integer>> arr= new ArrayList<>();
for(int i=0;i<n;i++){
ArrayList<Integer> a= new ArrayList<Integer>();
arr.add(a);
}
int odd=-1;
int a=0,b=0;
for(int i=0;i<m;i++){
st = new StringTokenizer(br.readLine());
a= Integer.parseInt(st.nextToken());
b= Integer.parseInt(st.nextToken());
arr.get(a-1).add(b-1);
arr.get(b-1).add(a-1);
}
// even edges
if(m%2==0){
System.out.println(1);
for(int i=0;i<n;i++){
System.out.print(1+" ");
}
System.out.println();
continue;
}
// odd edges
int odd=-1;
for(int i=0;i<n;i++){
if(arr.get(i).size()%2==1){
odd=i;
break;
}
}
if(odd!=-1){
System.out.println(2);
for(int j=0;j<n;j++){
if(j==odd){
System.out.print(1+" ");
}
else{
System.out.print(2+" ");
}
}
System.out.println();
}
else{
System.out.println(3);
for(int i=0;i<n;i++){
if(i==a-1){
System.out.print(1+" ");
}
else if(i==b-1){
System.out.print(2+" ");
}
else{
System.out.print(3+" ");
}
}
System.out.println();
}
}
br.close();
}
}