#include <stdio.h>
#include <string.h>
#include <vector>
#define NMax 10010

using namespace std;

const char IN[]="felinare.in",OUT[]="felinare.out";

int N,M,Sol;
int L[NMax],R[NMax];
bool visit[NMax] , S[2*NMax];
vector<int> ad[NMax];

bool pairup(int x)
{
	int i;
	if (visit[x]) return false;
	visit[x]=true;
	for (i=0;i<(int)ad[x].size();++i) if (!R[ad[x][i]])
	{
		L[x]=ad[x][i];
		R[ad[x][i]]=x;
		return true;
	}
	for (i=0;i<(int)ad[x].size();++i) if (pairup(R[ad[x][i]]))
	{
		L[x]=ad[x][i];
		R[ad[x][i]]=x;
		return true;
	}
	return false;
}

void calc(int x)
{
	for (int i=0;i<ad[x].size();++i)
		if ( !S[ad[x][i]+N] )
		{
			S[ad[x][i]+N]=true;
			S[R[ad[x][i]]]=false;
			calc(R[ad[x][i]]);
		}
}

int main()
{
	int i,x,y,c;
	freopen(IN,"r",stdin);
	scanf("%d%d",&N,&M);
	for (i=0;i<M;++i)
	{
		scanf("%d%d",&x,&y);
		ad[x].push_back(y);
	}
	
	for (c=1;c;)
	{
		c=0;
		memset(visit,0,sizeof(visit));
		for (i=1;i<=N;++i) if (!L[i])
			c|= pairup(i);
	}
	for (i=1;i<=N;++i) Sol+= (S[i]=L[i]!=0);
	
	for (i=1;i<=N;++i) if (!L[i])
		calc(i);
	
	freopen(OUT,"w",stdout);
	printf("%d\n",2*N-Sol);
	for (i=1;i<=N;++i)
		printf("%d\n", ((!S[N+i])<<1) + (!S[i]) );
	
	return 0;
}