> 爆搜+上下界剪纸
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int n,m,adj[555][555],num[555],ans[555],list[555],cnt_list,pre,st[555];
int queue[555],temp1,temp2,temp,e[2][255555];
bool vis[555],mark[555];
bool bfs(int id)
{
	int ip,i,j,s,p,q;
	st[id]=0;
	temp1=temp2=0;
	temp=1;
	queue[0]=id;
	while(temp1<=temp2)
	{
		for(i=temp1;i<=temp2;i++)
		{
			id=queue[i];
			for(j=0;j<num[id];j++)
			{
				ip=adj[id][j];
				if(mark[ip])
				{
					if(st[ip]<0)
					{
					   st[ip]=st[id]^1;
					   queue[temp++]=ip;
					}
					else if(st[ip]!=(st[id]^1))
			           return false;
				}
				else
				{
					if(st[ip]<0)
					   st[ip]=st[id]^1;
		            else if(st[ip]!=(st[id]^1)&&!vis[ip])
		            {
		            	vis[ip]=true;
            			list[cnt_list++]=ip;
		            }
				}
			}
		}
		temp1=temp2+1;
		temp2=temp-1;
	}
	for(i=0;i<n;i++)
	{
		if(!mark[i]&&st[i]>=0)
		   st[i]=-1;
	}
	return true;
}
bool check()
{
	int ip,id,i,j,s,p,q,ls[555],cnt_ls=0;
	memset(mark,false,sizeof(mark));
	for(i=0;i<cnt_list;i++)
	{
		id=list[i];
		for(j=0;j<num[id];j++)
		{
			ip=adj[id][j];
			if(!mark[ip])
			{
				mark[ip]=true;
				ls[cnt_ls++]=ip;
			}
		}
	} 
	memset(st,-1,sizeof(st));
	for(i=0;i<cnt_ls;i++)
	{
		if(st[ls[i]]<0)
		{
			if(!bfs(ls[i]))
			   return false;
		}
	}
	return true;
}
void color()
{
	int id,ip,i,j,s,p,q,ls[555],cnt_ls=0;
	memset(mark,false,sizeof(mark));
	for(i=0;i<cnt_list;i++)
	{
		id=list[i];
	    if(!mark[id])
	     	 mark[id]=true;	
	}
	for(i=0;i<n;i++)
	{
		if(!mark[i])
		  ls[cnt_ls++]=i;
	}
	memset(st,-1,sizeof(st));
	for(i=0;i<cnt_ls;i++)
	{
		id=ls[i];
		if(st[ls[i]]<0)
		{
			temp1=temp2=0;
			temp=1;
			queue[0]=id;
			st[id]=0;
			while(temp1<=temp2)
			{
				for(j=temp1;j<=temp2;j++)
				{
					id=queue[j];
					for(s=0;s<num[id];s++)
					{
						ip=adj[id][s];
						if(!mark[ip])
						{
							if(st[ip]<0)
							{
								st[ip]=st[id]^1;
								queue[temp++]=ip;
							}
							else if(st[ip]!=(st[id]^1))
				            {
            					while(true)
            					   puts("orz");
            				}
						}
					}
				}
				temp1=temp2+1;
				temp2=temp-1;
			}
		}
	}
	for(i=0;i<cnt_ls;i++)
		ans[ls[i]]=st[ls[i]]+1;
	for(i=0;i<cnt_list;i++)
		ans[list[i]]=0; 
}
bool check_upper_bound()
{
	int i,j,s,p,q,id,ip;
	memset(st,-1,sizeof(st));
	memset(mark,false,sizeof(mark));
	for(i=0;i<cnt_list;i++)
		mark[list[i]]=true;
	for(i=0;i<n;i++)
	{
		if(!mark[i]&&st[i]<0)
		{
			temp1=temp2=0;
			temp=1;
			queue[0]=i;
			st[i]=0;
			while(temp1<=temp2)
			{
				for(j=temp1;j<=temp2;j++)
				{
					id=queue[j];
					for(s=0;s<num[id];s++)
					{
						ip=adj[id][s];
						if(!mark[ip])
						{
							if(st[ip]<0)
							{
								st[ip]=st[id]^1;
							    queue[temp++]=ip;
							}
							else if(st[ip]!=(st[id]^1))
							   return false;
						}
					}
				}
				temp1=temp2+1;
				temp2=temp-1;
			}
		}
	}
	return true;
}
bool dfs(int id)
{
	int i,j,s,p,q,fr,ip;
	fr=cnt_list;
	list[cnt_list++]=id;
	memset(vis,false,sizeof(vis));
	pre=0;
	while(pre<cnt_list)
	{
		for(j=pre;j<cnt_list;j++)
		   vis[list[j]]=true;
        pre=cnt_list;
        if(!check())
        {
       	   cnt_list=fr;
       	   memset(vis,false,sizeof(vis));
           for(i=0;i<cnt_list;i++)
       	   {
   	       	    vis[list[i]]=true;
   	       	    for(j=0;j<num[list[i]];j++)
   	       	        vis[adj[list[i]][j]]=true;
   	       }
           return false;
        }
		for(j=0;j<n;j++)
        {
        	if(mark[j])
        	   vis[j]=true;
        }
	}
	if(check_upper_bound())
	{
		color();
	    return true;
	}
	memset(vis,false,sizeof(vis));
	for(i=0;i<cnt_list;i++)
    {
    	ip=list[i];
    	vis[ip]=true;
    	for(j=0;j<num[ip];j++)
	    	vis[adj[ip][j]]=true;
    }
    for(i=id+1;i<n;i++)
    {
    	if(!vis[i])
 	    {
    	 	if(dfs(i))
    	 	   return true;
        }
    }
    cnt_list=fr;
    memset(vis,false,sizeof(vis));
	for(i=0;i<cnt_list;i++)
    {
    	vis[list[i]]=true;
    	for(j=0;j<num[list[i]];j++)
    	   vis[adj[list[i]][j]]=true;
    }
    return false;
}
bool fill()
{
	int i,j,s,p,q,cnt=0,fr,id;
	list[0]=0;
	ans[0]=0;
	pre=0;
	cnt_list=1;
	memset(vis,false,sizeof(vis));
	while(pre<cnt_list)
	{
		for(i=pre;i<cnt_list;i++)
		   vis[list[i]]=true;
        pre=cnt_list;
		if(!check())
		   return false;
        for(i=0;i<n;i++)
        {
        	if(mark[i])
        	   vis[i]=true;
        }
	}
	for(i=pre;i<cnt_list;i++)
	   vis[list[i]]=true;
	if(check_upper_bound())
	{
		color();
	    return true; 
	}
	for(i=0;i<n;i++)
	{
		if(!vis[i])
		{
			if(dfs(i))
			   return true;
		}
	}
	return false;
}
int main()
{
	int i,j,s,p,q,id1,id2;
	while(scanf("%d%d",&n,&m)&&(n||m))
	{ 
	    memset(num,0,sizeof(num));
		for(i=0;i<m;i++)
		{
			scanf("%d%d",&id1,&id2);
			adj[id1][num[id1]++]=id2;
			adj[id2][num[id2]++]=id1;
		}
		if(fill())
		{
			for(i=0;i<n;i++)
			   printf("%d ",ans[i]);
            printf("\n");
		}
		else
		   printf("The agents cannot be split\n");
	}
}