#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;
bitset< N_MAX > wasVist;
vector< int > G[N_MAX];
inline bool PairUp( int x )
{
	if( wasVist.test(x) )
		return false;
	wasVist.flip(x);
	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;
			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.test(*it) )
		{
			SM.flip(*it);
			SM.flip(R[*it]);
			SuportMinim( R[*it] );
		}
}
int main( void )
{
	bool ok;
	int N, M, x, y, _count=0;
	ifstream in( "felinar.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, SM.flip(x);
		wasVist&=0;
	}while( ok );
	for( x=1; x <= N; ++x )
		if( !L[x] )
			SuportMinim(x);
	ofstream out( "felinar.out" );
	out<<(2*N-SM.count())<<'\n';
	for( x=1; x <= N; ++x )
		if( SM.test(x) )
			out<<"2\n";
		else out<<"3\n";
	return EXIT_SUCCESS;
}