#include <stdio.h>

int main(void) {
    int i,j,a,b,agg,rad,nejde;
    int sk1[500], sk2[500], sk3[500];
    
    int hate[10000][2];
    
    for(i=0;i<500;i++) {
	sk1[i] = sk2[i] = sk3[i] = 1;
    }
    
    while(1) {
	scanf("%d %d\n",&a,&b);
	if (a == 0 && b == 0) return 0;
	for(i=0; i<b; i++) {
	    scanf("%d %d\n",&hate[i][0],&hate[i][1]);
	}
	
	for(i=0;i<a;i++){
	    if (sk1[i]) {
		for(j=0; j<b; j++) {
		    if (hate[j][0] == i) sk1[hate[j][1]] = 0;
		    if (hate[j][1] == i) sk1[hate[j][0]] = 0;
		}
	    }
	}
	for(i=0;i<a;i++)
	    if (sk1[i]) {
		sk2[i] = 0;
		sk3[i] = 0;
	    }
	    
	for(i=0;i<a;i++){
	    if (sk2[i]) {
		for(j=0; j<b; j++) {
		    if (hate[j][0] == i) sk2[hate[j][1]] = 0;
		    if (hate[j][1] == i) sk2[hate[j][0]] = 0;
		}
	    }
	}
	for(i=0;i<a;i++)
	    if (sk2[i]) 
		sk3[i] = 0;
	
	for(i=0;i<a;i++){
	    if (sk3[i]) {
		for(j=0; j<b; j++) {
		    if (hate[j][0] == i) sk3[hate[j][1]] = 0;
		    if (hate[j][1] == i) sk3[hate[j][0]] = 0;
		}
	    }
	}

	nejde = 0;
	for (i=0;i<a;i++) 
	    if (!(sk1[i] || sk2[i] || sk3[i] )) {
		nejde = 1;
	    }        
	    
	if (!nejde) 
	    for (i=0;i<a;i++) {
		if (sk1[i]) printf("%d ", 0);
		if (sk2[i]) printf("%d ", 1);
		if (sk3[i]) printf("%d ", 2);
	    }
	else
	    printf("The agents cannot be split");
	      
	printf("\n");      
	    
	scanf("\n");
    }
}