#include<fstream>
#include<vector>
#include<string.h>
#define inf "felinare.in"
#define outf "felinare.out"
#define NMax 9000
#define MMax 20100
using namespace std;

fstream f(inf,ios::in), g(outf,ios::out);

int N, M;
int L[NMax], R[NMax], viz[NMax];
int sl[NMax], sr[NMax];
vector<int> LA[NMax];

void read()
{
	f>>N>>M; int a,b;
	for(int i=1; i<=M; i++)
	{
		f>>a>>b;
		LA[a].push_back(b);
	}
}

bool pairUp(int u)
{
	if( viz[u] ) return false;
	viz[u] = 1;
	for(int i=0; i<LA[u].size(); i++)
	{
		int v = LA[u][i];
		if( !R[v] || pairUp(R[v]) )
		{
			L[u] = v; R[v] = u;
			return true;
		}
	}
	return false;
}

int cuplaj()
{
	bool ok = true; int c = 0;
	while( ok )
	{
		ok = false; memset(viz, 0, sizeof(viz));
		for(int i=1; i<=N; i++)
			if( !L[i] && pairUp(i) ) c++, ok = true;
	}
	return c;
}

void pairUp2(int u)
{
	for(int i=0; i<LA[i].size(); i++)
	{
		int v = LA[u][i];
		if( !sr[v] )
		{
			sr[v] = 1; sl[ R[v] ] = 0;
			pairUp2(R[v]);
		}
	}
}

void suport_minim()
{
	for(int i=1; i<=N; i++)
		if( L[i] ) sl[i] = 1;
	for(int i=1; i<=N; i++)
		if( !L[i] ) pairUp2(i);
}

void solve()
{
	int c = cuplaj();
	suport_minim();
	g<< 2*N - c <<"\n";
	for(int i=1; i<=N; i++)
	{
		if( sl[i] )
		{
			if( sr[i] ) g<<"0";
			else g<<"2";
		}
		else
		{
			if( sr[i] ) g<<"1";
			else g<<"3";
		}
		g<<"\n";
	}
}

int main()
{
	read(); solve();
	f.close(); g.close();
	return 0;
}