#include <stdio.h>
#include <vector>

using namespace std;

#define FOR(i,s,d) for(i=(s);i<(d);++i)
#define sz size()
#define nmax 8192

vector <int> G[nmax];
int n,m,viz[nmax],R[nmax],p[nmax];

int pairup(int i)
{
	int j;
	if(viz[i])
		return 0;
	viz[i]=1;
	FOR(j,0,G[i].sz)
		if(!R[G[i][j]]||pairup(R[G[i][j]]))
		{
			R[G[i][j]]=i; p[i]=G[i][j];
			return 1;
		}
	return 0;
}

void marc(int i)
{
	if(viz[i]&1)
		return ;
	viz[i]|=1;
	int j;
	FOR(j,0,G[i].sz)
		viz[G[i][j]]&=1,marc(R[G[i][j]]);
}

int main()
{
	int ii,i,j;
	freopen("felinare.in","r",stdin);
	freopen("felinare.out","w",stdout);
	scanf("%d %d",&n,&m);
	FOR(ii,0,m)
	{
		scanf("%d %d",&i,&j);
		G[i].push_back(j);
	}
	j=0;
	FOR(i,1,n+1)
	{
		memset(viz,0,sizeof(viz));
		j+=pairup(i);
	}
	printf("%d\n",2*n-j);
	FOR(i,1,n+1)
		viz[i]=2;
	FOR(i,1,n+1)
		if(!p[i])
			marc(i);
	FOR(i,1,n+1)
		printf("%d\n",viz[i]);
	return 0;
}