#include<fstream>
#include<vector>

#define maxn 8194

using namespace std;

ifstream fin("felinare.in");
ofstream fout("felinare.out");

int n,m,S,T,cuplaj;
int c[maxn],u[maxn],pus[maxn];

vector < int > v[maxn];

void citire()
{	int i,x,y;
	fin>>n>>m;

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

int cup(int nod)
{	int i;
	if(u[nod]) return 0;
	u[nod]=1;
	for(i=0;i<(int)v[nod].size();i++)
		if(!c[v[nod][i]]||cup(c[v[nod][i]]))
		{	c[nod]=v[nod][i];
			c[v[nod][i]]=nod;
			return 1;
		}
	return 0;
}

void calculeaza(int nod)
{	for(int i=0;i<(int)v[nod].size();i++)
		if(pus[v[nod][i]]==0)
		{	pus[v[nod][i]]=1;
			pus[c[v[nod][i]]]=0;
			calculeaza(c[v[nod][i]]);
		}
}
			

int main()
{	int i,cont=1;

	citire();
	
	while(cont)
	{	cont=0;
		for(i=1;i<=n;i++)
			u[i]=0;
		for(i=1;i<=n;i++)
			if(!c[i]) cont+=cup(i);
	}
	for(i=1;i<=n;i++)
		if(c[i]) { cuplaj++;
					pus[i]=1;
				  }
	fout<<2*n-cuplaj<<"\n";
	for(i=1;i<=n;i++)
		if(!pus[i])
			calculeaza(i);
	for(i=1;i<=n;i++)
	{	int	rasp=0;
		if(!pus[i])
			rasp+=1;
		if(!pus[i+n])
			rasp+=2;
		fout<<rasp<<"\n";
	}
	fin.close();
	fout.close();
	return 0;
}