#include<fstream>
#include<vector>
#include<cstring>
#define NM 9000
using namespace std;
ifstream f("felinare.in");
ofstream g("felinare.out");
int i,n,j,m,x,y,L[NM],R[NM],nrc,ok;
int st[NM],dr[NM],viz[NM];
vector<int> v[NM];
void Citire()
{
	f>>n>>m;
	for(i=1;i<=m;++i)
	{
		f>>x>>y;
		v[x].push_back(y);
	}
}
int Cupleaza(int x)
{
	if(viz[x])return 0;
	viz[x]=1;
	for(int i=0;i<v[x].size();++i)
		if(!L[v[x][i]])
		{
			L[v[x][i]]=x;
			R[x]=v[x][i];
			return 1;
		}
	for(int i=0;i<v[x].size();++i)
		if(Cupleaza(L[v[x][i]]))
		{
			L[v[x][i]]=x;
			R[x]=v[x][i];
			return 1;
		}
	return 0;
}
void Cuplaj()
{
	ok=1;
	while(ok)
	{
		ok=0;
		memset(viz,0,n+1);
		for(j=1;j<=n;++j)
			if(!R[j])
				if(Cupleaza(j))
				{
					ok=1;
					nrc++;
				}
	}
}
void Consuma(int x)
{
	for(int j=0;j<v[x].size();++j)
		if(!dr[v[x][j]])
		{
			dr[v[x][j]]=1;
			st[L[v[x][j]]]=0;
			Consuma(L[v[x][j]]);
		}
}
void Rezolva()
{
	for(i=1;i<=n;++i)
		if(R[i])
			st[i]=1;
	for(i=1;i<=n;++i)
		if(!R[i])
			Consuma(i);
}
void Scrie()
{
	g<<2*n-nrc<<"\n";
	for(i=1;i<=n;++i)
	{
		if(!st[i]&&!dr[i])
			g<<"3\n";
		else
		if(!st[i])
			g<<"1\n";
		else
		if(!dr[i])
			g<<"2\n";
		else
			g<<"0\n";
	}
}
int main ()
{
	Citire();
	Cuplaj();
	Rezolva();
	Scrie();
	return 0;
}