#include <stdio.h>

int a[600][600];
int b[600];
int m[600][3];

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++) a[i][0]=0;
		for (i=0;i<d;i++)
		{
			scanf("%d %d",&k,&j);
			a[k][++a[k][0]]=j;a[j][++a[j][0]]=k;
		}
		for (i=0;i<n;i++) b[i]=-1;
		b[0]=0;
		for (i=1;i<n;i++)
		{
			for (j=0;j<n;j++) if (b[j]==-1)
			{
				m[j][0]=m[j][1]=m[j][2]=1;
				p=a[j][0];
				for (k=1;k<=p;k++) if (b[a[j][k]]!=-1)
				m[j][b[a[j][k]]]=0;
				if (m[j][0]+m[j][1]+m[j][2]<=1) break;
			}
			if (j<n && m[j][0]+m[j][1]+m[j][2]==0) break;
			if (j<n)
			{
				k=0;
				while (m[j][k]==0) k++;
				b[j]=k;
				continue;			
			}
			for (j=0;j<n;j++) if (b[j]==-1) if (m[j][0]+m[j][1]+m[j][2]==2) break;
			if (j<n)
			{
				k=0;
				while (m[j][k]==0) k++;
				b[j]=k;
				continue;			
			}
			for (j=0;j<n;j++) if (b[j]==-1) break;
			b[j]=0;						
		}
		if (i<n) printf("The agents cannot be split\n"); else
		{
			for (i=0;i<n;i++) printf("%d ",b[i]);
			printf("\n");
		}
	}
	return 0;
}