#include<fstream>
#include<vector>
using namespace std;
int n,m,nrcuplaj;
vector <int> G[8200];
int st[8200],dr[8200];
bool viz[8200],suportL[8200],suportR[8200];

inline void Citire()
{
	int i,x,y;
	ifstream fin("felinare.in");
	fin>>n>>m;
	for(i=1;i<=m;i++)
	{
		fin>>x>>y;
		G[x].push_back(y);
	}
	fin.close();
}

inline bool HopcroftKarp(int x)
{
	vector <int>::iterator it;
	for(it=G[x].begin();it!=G[x].end();it++)
	{
		if(!st[*it])
		{
			st[*it]=x;
			dr[x]=*it;
			nrcuplaj++;
			return true;
		}
	}
	for(it=G[x].begin();it!=G[x].end();it++)
	{
		if(HopcroftKarp(st[*it]))
		{
			st[*it]=x;
			dr[x]=*it;
			nrcuplaj++;
			return true;
		}
	}
	return false;
}

inline void CuplajMaxim()
{
	int i;
	bool modificare=true;
	while(modificare)
	{
		modificare=false;
		for(i=1;i<=n;i++)
			if(!dr[i])
				modificare|=HopcroftKarp(i);
		for(i=1;i<=n;i++)
			viz[i]=false;
	}
}

inline void SuportMinim(int x)
{
	vector <int>::iterator it;
	for(it=G[x].begin();it!=G[x].end();it++)
	{
		if(!suportR[*it])
		{
			suportR[*it]=true;
			suportL[st[*it]]=false;
			SuportMinim(st[*it]);
		}
	}
}

inline void Rezolvare()
{
	int i;
	for(i=1;i<=n;i++)
		if(dr[i])
			suportL[i]=true;
	for(i=1;i<=n;i++)
		if(!dr[i])
			SuportMinim(i);
}

inline void Afisare()
{
	int i;
	ofstream fout("felinare.out");
	fout<<(2*n-nrcuplaj)<<"\n";
	for(i=1;i<=n;i++)
	{
		if(!suportL[i] && !suportR[i])
			fout<<"3\n";
		if(suportL[i] && !suportR[i])
			fout<<"2\n";
		if(!suportL[i] && suportR[i])
			fout<<"1\n";
		if(suportL[i] && suportR[i])
			fout<<"0\n";
	}
	fout.close();
}

int main()
{
	Citire();
	CuplajMaxim();
	Rezolvare();
	Afisare();
	return 0;
}