#include<stdio.h>
#define N 8200
void read(),solve(),pune(),cuplaj(),calculeaza(int k),print();

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

int n,m,i,a,b,sol,j,ci[N],cd[N],viz[N],creste(int st),gata,ss[N],sd[N];

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();}
}
void pune()
{	paux=new nod;
	paux->inf=b; paux->next=vec_out[a]; vec_out[a]=paux;
}

void solve()
{	cuplaj();
	 for(i=1;i<=n;i++) if(cd[i]) ss[i]=1;
	 for(i=1;i<=n;i++) if(!cd[i]) calculeaza(i);
}

void cuplaj()
{
	gata=0;
	while(!gata)
	{
		gata=1;
		for(i=1;i<=n;i++) viz[i]=0;
		for(i=1;i<=n;i++)
			if(!cd[i]&&creste(i))gata=0;
	}
	for(i=1;i<=n;i++)if(cd[i])sol++;
	printf("%d\n",2*n-sol);
}

int creste(int st)
{	nod *ppaux;
	if(viz[st]) return 0;
	viz[st]=1;
	for(ppaux=vec_out[st];ppaux;ppaux=ppaux->next)
		if(!ci[ppaux->inf]){ ci[ppaux->inf]=st; cd[st]=ppaux->inf; return 1;}
	for(ppaux=vec_out[st];ppaux;ppaux=ppaux->next)
		if(creste(ci[ppaux->inf])){ ci[ppaux->inf]=st; cd[st]=ppaux->inf; return 1;}
	return 0;
}

void calculeaza(int k)
{	nod *ppaux;
	for(ppaux=vec_out[k];ppaux;ppaux=ppaux->next)
		if(!sd[ppaux->inf]) { sd[ppaux->inf]=1;
							  ss[ci[ppaux->inf]]=0;
		                      calculeaza(ci[ppaux->inf]);
							}
}

void print()
{
	int bec[2][2]={{3,1},{2,0}};
	for(i=1;i<=n;i++)
	    printf("%d\n",bec[ss[i]][sd[i]]);
}