#include<fstream>
#include<vector>
#include<cstring>

#define pb push_back
#define NN 8200

using namespace std;
ofstream out("felinare.out");

int st[NN],dr[NN],n,m,uz[NN],cuplaj,sst[NN],sdr[NN];
vector<int>G[NN];
typedef vector<int>::iterator IT;

void read();
int pairup(int );
void facuplaj();
void suport(int);

int main()
{
	read();
	facuplaj();
	out<<2*n-cuplaj<<'\n';
	for(int i=1;i<=n;i++)
		{
			if(sst[i])
				if(sdr[i])
					out<<0;
				else
					out<<2;
			else
				if(sdr[i])
					out<<1;
				else
					out<<3;
				out<<'\n';
	}
	
	
	return 0;
}


void read()
{
	ifstream in("felinare.in");
	in>>n>>m;
	for(int x,y,i=1;i<=m;i++)
	{
		in>>x>>y;
		G[x].pb(y);
	}
}

int pairup(int start)
{
	if(uz[start])
		return 0;
	uz[start]=1;
	for(IT I=G[start].begin();I!=G[start].end();++I)
		if(!st[*I] || pairup(st[*I]))
		{
			st[*I]=start;
			dr[start]=*I;
			sst[start]=1;
			return 1;
		}
		return 0;
}

void facuplaj()
{
	int ok=1;
	while(ok)
	{
		ok=0;
		memset(uz,0,sizeof(uz));
		for(int i=1;i<=n;i++)
			if(!dr[i])
				if(pairup(i))
					{
						++cuplaj;
						ok=1;
				}
	}
}

void suport(int start)
{
	for(IT I=G[start].begin();I!=G[start].end();++I)
		if(!sdr[*I])
		{
			sdr[*I]=1;
			sst[st[*I]]=0;
			suport(st[*I]);
		}
}