#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream fin("felinare.in");
ofstream fout("felinare.out");
#define dim 20006
vector <int> v[dim];
int viz[dim],a[dim], b[dim],n,m,sol[dim*2];

void read()
{
	int i, x, y;
	fin>>n >>m;
	for(i=1;i<=m;++i)
	{
		fin>>x >>y;
		v[x].push_back(y);
	}
}

int pairup(int nod)
{
	if(viz[nod])
		return 0;
	viz[nod]=1;
	
	for(int k=0;k<(int)v[nod].size();++k)
		if(!b[v[nod][k]])
		{
			a[nod]=v[nod][k];
			b[v[nod][k]]=nod;
			return 1;
		}
	for(int k=0;k<(int)v[nod].size();++k)
		if(pairup(b[v[nod][k]]))
		{
			a[nod]=v[nod][k];
			b[v[nod][k]]=nod;
			return 1;
		}
	
	return 0;
}

void df(int nod)
{
	for(int k=0;k<(int)v[nod].size();++k)
		if(viz[v[nod][k]]==0)
		{
			viz[v[nod][k]]=1;
			sol[b[v[nod][k]]]=0;
			df(b[v[nod][k]]);
		}
}

void solve()
{
	int  ok;
	int nr=0;
	do
	{
		ok=0;
		memset(viz,0,sizeof(viz));
		for(int i=1;i<=n;++i)
			if(!a[i] && pairup(i))
			{
				ok=1;
				++nr;
			}
		
	}while(ok);
	
	fout<<n*2-nr <<'\n';
	
	int i;
	
	memset(viz,0,sizeof(viz));
	for(i=1;i<=n;++i)
		if(a[i]!=0)
			sol[i]=1;
	
	for(i=1;i<=n;++i)
		if(a[i]==0)
			df(i);
}

void print()
{
	int i;
	for(i=1;i<=n;++i)
		if(sol[i] && viz[i])
			fout<<"0\n";
		else
			if(sol[i]==0 && viz[i]!=0)
				fout<<"1\n";
			else
				if(sol[i]!=0 && viz[i]==0)
					fout<<"2\n";
				else
					fout<<"3\n";
}

int main()
{
	read();
	solve();
	print();
	return 0;
}