#include <cstdio>
#include <cstring>

FILE* in=fopen("felinare.in","r");
FILE* out=fopen("felinare.out","w");

const int Q=20007;

int lst[Q],val[Q],nxt[Q],nr;

void add(int a, int b)
{
	val[++nr]=b;
	nxt[nr]=lst[a];
	lst[a]=nr;

}

int to[Q],frm[Q];
bool viz[Q];

bool cuplaj(int x)
{
	viz[x]=1;

	for(int p=lst[x]; p; p=nxt[p])
	{
		if(frm[val[p]]==0)
		{
			to[x]=val[p];
			frm[val[p]]=x;
			return 1;
		}
	}

	for(int p=lst[x]; p; p=nxt[p])
	{
		if(viz[frm[val[p] ] ]==0 && cuplaj(frm[val[p]]))
		{
			to[x]=val[p];
			frm[val[p]]=x;
			return 1;
		}
	}

	return 0;
}

int n,m;

int rez[Q];

void calculeaza(int x)
{
	rez[x]--;
	for(int p=lst[x]; p; p=nxt[p])
	{
		if(val[p]==to[x])
			continue;

		if((rez[val[p]]&2)==0 )
		{
			rez[val[p]]+=2;

			if((rez[frm[val[p]]]&1)==1)
				calculeaza(frm[val[p]]);
		}
	}
}

void finise()
{

	for(int i=1; i<=n; i++)
	{
		rez[i]=1;
	}

	for(int i=1; i<=n; i++)
	{
		if((rez[i]&1)==1 && to[i]==0)
		{
			calculeaza(i);
		}
	}

}


int main()
{
    fscanf(in,"%d%d",&n,&m);

    int a,b;

    for(int i=1; i<=m; i++)
    {
		fscanf(in,"%d%d",&a,&b);

		add(a,b);
    }

	int r=2*n;

    while(true)
    {
		bool bun=0;

		for(int i=1; i<=n; i++)
		{
			if(viz[i]==0 && to[i]==0 && cuplaj(i))
			{
				bun=1;
				r--;
			}
		}
		if(bun==0)
			break;
		memset(viz,0,sizeof viz);
    }

	fprintf(out,"%d\n",r);


	//memset(viz,0,sizeof viz);

    finise();

    for(int i=1; i<=n; i++)
	{
		fprintf(out,"%d\n",3-rez[i]);
	}

    return 0;
}