#include<fstream.h>

struct nod{ int info,flux,cap,cost; nod *next; nod () { info=flux=0;cap=1; next=0; } };

nod *v[20000];

int F,n,m,C[17000],sw[20000],left[10000],t[20000],dr[10000],N;

void cupleaza(int k)
{
	nod *q;
	for (q=v[k];q;q=q->next)
		if (!q->info && !sw[q->info])
		{
			sw[left[q->info-n]]=0;
			sw[q->info]=1;
			cupleaza (left[q->info-n]);
		}
}
void suport()
{
	int i;
	for (i=1;i<=n;i++)
		dr[left[i]]=i;
	memset(sw,0,sizeof(sw));
	
	for (i=1;i<=n;i++)
		if (dr[i]>0)
			sw[i]=1;
	
	for (i=1;i<=n;i++)
		if (sw[i]==0)
			cupleaza(i);
}

void afisare ()
{
	int i,p;
	ofstream g("felinare.out");
	g<<2*n-F<<'\n';
	for (i=1;i<=n;i++)
	{
		p=0;
		if (sw[i]==0) p++;
		if (sw[i+n]==0) p+=2;
		g<<p<<'\n';
	}
	g.close();
}

void getflux ()
{
	int i,h,p,u,r,sw1;
	nod *q;
	for (i=0;i<=N;i++)
		t[i]=sw[i]=0;
	p=1;
	u=1;
	sw[0]=1;
	C[p]=0;
	while (p<=u)
	{
		h=C[p];
		for (q=v[h];q;q=q->next)
			if (sw[q->info]==0 && q->cap >= q->flux+1 && q->info!=N)
			{
				t[q->info]=h;
				C[++u]=q->info;
				sw[q->info]=1;
			}
		p++;
	}
	for (i=n+1;i<N;i++)
	{
		for (q=v[i];q->info!=N;q=q->next);
		if (sw[i]==1 && q->cap >= q->flux +1)
		{
			sw1=0;
			r=i;
			for (;r>0;r=t[r])
			{
				for (q=v[t[r]];q->info!=r;q=q->next);
				if (q->cap < q->flux+1)
					sw1=1;
			}
			if (!sw1)
			{
				r=i;
				for (q=v[i];q->info!=N;q=q->next);
				q->flux=1;
				for (;r>0;r=t[r])
				{
					for (q=v[t[r]];q->info!=r;q=q->next);
					q->flux++;
					if (t[r]>0){
					for (q=v[r];q->info!=t[r];q=q->next);
					q->flux--;}
					if (r>n) left[r-n]=t[r];
				}
				F++;
			}
		}
	}
}
void fluxmax()
{
	int f;
	f=-1;
	while (F-f>0)
	{
		f=F;
		getflux();
	}
}
	
void citire ()
{
	int i,x,y;
	nod *p;
	ifstream f("felinare.in");
	f>>n>>m;
	N=2*n+1;
	for (i=0;i<=N;i++)
		v[i]=0;
	
	for (i=1;i<=m;i++)
	{
		f>>x>>y;
		p=new nod;
		p->info=y+n;
		p->next=v[x];
		v[x]=p;
		
		p=new nod;
		p->info=x;
		p->cap=0;
		p->next=v[y+n];
		v[y+n]=p;
	}
	
	for (i=1;i<=n;i++)
	{
		p=new nod;
		p->info=i;
		p->next=v[0];
		v[0]=p;
		
		p=new nod;
		p->info=N;
		p->next=v[i+n];
		v[i+n]=p;
	}
}

int main()
{
	citire ();
	fluxmax();
	suport();
	afisare();
	return 0;
}