#include <bitset>
#include <vector>
#include <fstream>
#include <cstdlib>
#define N_MAX 8201

using namespace std;
int L[N_MAX], R[N_MAX];
bitset< N_MAX > SM, Cup, was;
vector< int > G[N_MAX];
inline bool PairUp( int x )
{
	if( was[x] )
		return false;
	was[x]=true;
	vector< int >::const_iterator it=G[x].begin(), iend=G[x].end();
	for( ; it < iend; ++it )
		if( !R[*it] || PairUp(R[*it]) )
		{
			R[*it]=x;
			L[x]=*it;
			Cup[x]=true;
			return true;
		}
	return false;
}
inline void SuportMinim( int x )
{
	vector< int >::const_iterator it=G[x].begin(), iend=G[x].end();
	for( ; it < iend; ++it )
		if( false == SM[*it] )
		{
			SM[*it]=true;
			Cup[R[*it]]=false;
			SuportMinim( R[*it] );
		}
}
int main( void )
{
	bool ok;
	int N, M, x, y;
	ifstream in( "felinare.in" );
	for( in>>N>>M; M; --M )
	{
		in>>x>>y;
		G[x].push_back(y);
	}
	do
	{
		ok=false;
		for( x=1; x <= N; ++x )
			if( !L[x] && PairUp(x) )
				ok=true;
		was&=0;
	}while( ok );
	for( x=1; x <= N; ++x )
		if( !Cup[x] )
			SuportMinim(x);
	ofstream out( "felinare.out" );
	out<<(2*N-Cup.count()+SM.count())<<'\n';
	for( x=1; x <= N; ++x )
		if( Cup[x] && SM[x] )
			out<<"0\n";
		else if( !Cup[x] && SM[x] )
				out<<"1\n";
			 else if( !SM[x] && Cup[x] )
					out<<"2\n";
				  else out<<"3\n";
	return EXIT_SUCCESS;
}