#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)
{
	for(int p=lst[x]; p; p=nxt[p])
	{
		if((rez[val[x]]&2)==0 && frm[val[x]])
		{
			rez[val[x]]-=2;
			rez[frm[val[x]]]+=1;
			calculeaza(frm[val[x]]);
		}
	}
}

void finise()
{
	for(int i=1; i<=n; i++)
	{
		if(to[i])
		{
			rez[i]=2;
		}
		else
		{
			rez[i]=3;
		}
	}

	for(int i=1; i<=n; i++)
	{
		if(!rez[i]&1)
		{
			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);

    finise();

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

    return 0;
}