#include <fstream>
using namespace std;
ifstream fin("felinare.in");
ofstream fout("felinare.out");

#include <vector>
#define pb push_back
#define maxn 8200

int i,N,M,Cmax;
int S[maxn],D[maxn],v[maxn],sL[maxn],sR[maxn];
vector <int> A[maxn];

void citire()
{
	int x,y;
	fin >> N >> M;
	for(i=1;i<=M;i++)
	{
		fin >> x >> y;
		A[x].pb(y);
	}
}

int pairup(int x)
{
	vector <int> :: iterator it;
	if(v[x]) return 0;
	v[x]=1;
	for(it=A[x].begin();it!=A[x].end();it++)
		if(S[*it]==0 || pairup( S[*it] ) )
		{
			S[*it]=x; D[x]=*it; sL[x]=1; return 1;
		}
	return 0;
}

void cuplaj()
{
	int ok=1;
	while(ok)
	{
		ok=0;
		for(i=1;i<=N;i++) v[i]=0;
		for(i=1;i<=N;i++)
			if(D[i]==0)
				if( pairup(i) )
				{
					Cmax++;
					ok=1;
				}
	}
}

void suport(int x)
{
	vector <int> :: iterator it;
	for(it=A[x].begin();it!=A[x].end();it++)
		if(!sR[*it])
		{
			sR[*it]=1;
			sL[S[*it]]=0;
			suport(S[*it]);
		}	
}

void afisare()
{
	fout << 2*N-Cmax << '\n';
	for(i=1;i<=N;i++)
	{
		if(sL[i])
			if(sR[i])
				fout << '0';
			else fout << '2';
		else
			if(sR[i])
				fout << '1';
			else fout << '3';
		fout << '\n';
	}
}

int main()
{
	citire();
	cuplaj();
	for(i=1;i<=N;i++)
		if(!sL[i])
			suport(i);
	afisare();
}