#include <stdio.h>

int a[600][600];
int b[500];

int main()
{
	int d,n,i,j,k,p;
	while(1)
	{
		scanf("%d %d",&n,&d);
		if (n==0 && d==0) break;
		for (i=0;i<n;i++) for (j=0;j<n;j++) a[i][j]=0;
		for (i=0;i<d;i++)
		{
			scanf("%d %d",&k,&j);
			a[k][j]=1;a[j][k]=1;
		}
		for (i=0;i<n;i++) b[i]=-1;
		for (i=0;i<n;i++) if (b[i]==-1)
		{
			for (j=0;j<n;j++) if (a[i][j] && b[j]==1) break;
			if (j>=n) b[i]=1;
		}
		for (i=0;i<n;i++) if (b[i]==-1)
		{
			for (j=0;j<n;j++) if (a[i][j] && b[j]==2) break;
			if (j>=n) b[i]=2;
		}
		for (i=0;i<n;i++) if (b[i]==-1)
		{
			for (j=0;j<n;j++) if (a[i][j] && b[j]==3) break;
			if (j>=n) b[i]=3;
		}
		for (i=0;i<n;i++) if (b[i]==-1) break;
		if (i<n) printf("The agents cannot be split\n"); else
		{
			for (i=0;i<n;i++) printf("%d ",b[i]-1);
			printf("\n");
		}
	}
	return 0;
}