#include<stdio.h>
#define N 8200
void read(),solve(),pune(),sort(),hd(int ii, int nn),sw(int i1, int i2),print();

struct nod{ int inf; nod *next;};
nod *vec_in[N],*vec_out[N],*paux;

int n,m,i,gr_in[N],gr_out[N],a,b,fout[N],fin[N],poz_in[N],poz_out[N],*gr,*poz,sol,j;

int main()
{	read();
	solve();
	print();		
	return 0;
}

void read()
{	freopen("felinare.in","r",stdin);
	freopen("felinare.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++){ scanf("%d%d",&a,&b); pune(); gr_in[b]++; gr_out[a]++;}
}
void pune()
{	paux=new nod;
	paux->inf=b; paux->next=vec_out[a]; vec_out[a]=paux;
	paux=new nod;
	paux->inf=a; paux->next=vec_in[b]; vec_in[b]=paux;
}

void solve()
{	for(i=1;i<=n;i++) poz_in[i]=poz_out[i]=i;
	 
	gr=gr_in; poz=poz_in;
	sort();
	gr=gr_out; poz=poz_out;
	sort();
    
	i=1; j=1;
	while(i<=n&&j<=n)
	{    //1=aprins    -1=stins
		if(!gr_in[i]){fin[poz_in[i]]=1; i++; sol++; continue;}
		if(!gr_out[j]){fout[poz_out[j]]=1; j++; sol++; continue;}
		
		if(gr_in[i]<gr_out[j])
		{  if(!fin[poz_in[i]]){
				     				fin[poz_in[i]]=1;  sol++;
									for(paux=vec_in[poz_in[i]];paux;paux=paux->next)
								        fout[paux->inf]=-1; 
		                        }
		    i++;
			continue;
		}
		if(!fout[poz_out[j]]){
                     			    fout[poz_out[j]]=1; sol++;
							        for(paux=vec_out[poz_out[j]];paux;paux=paux->next)
								        fin[paux->inf]=-1;
		                      }
		j++;
	}
	while(i<=n)
	{	if(!fin[poz_in[j]]){
				     				fin[poz_in[i]]=1;  sol++;
									for(paux=vec_out[poz_in[j]];paux;paux=paux->next)
								        fout[paux->inf]=0;
		                        }
	    i++;
	}
	while(j<=n)
	{      if(!fout[poz_out[j]]){
                     			    fout[poz_out[j]]=1; sol++;
							        for(paux=vec_in[poz_out[j]];paux;paux=paux->next)
								        fin[paux->inf]=0;
									
		                        }
	        j++;
	}
}

void sort()
{
	for(i=n/2;i>=1;i--) hd(i,n);
	for(i=n;i>=1;i--){ sw(1,i); hd(1,i-1);}
}
void hd(int ii, int nn)
{
	int is=ii*2;
	if(is>nn) return;
	if(is<nn) if(gr[is]<gr[is+1]) is++;
	if(gr[ii]<gr[is]){ sw(ii,is); hd(is,nn);}
}
void sw(int i1, int i2)
{
	int
	aux=gr[i1]; gr[i1]=gr[i2]; gr[i2]=aux;
	aux=poz[i1]; poz[i1]=poz[i2]; poz[i2]=aux;
}

void print()
{
	printf("%d\n",sol);
	for(i=1;i<=n;i++)
	{	if(fout[i]<1){ if(fin[i]<1){ printf("0\n"); continue; }
                       printf("2\n"); continue;
	                 }
	    if(fin[i]<1) { printf("1\n"); continue;}
		printf("3\n");
	}
}