#include<cstdio>
#include<vector>
#include<bitset>

using namespace std;

const int MaxN = 8200;
const char InFile[] = "felinare.in";
const char OutFile[] = "felinare.out";

int N,M,cnt,lt[MaxN],rt[MaxN];
vector< vector<int> > G;
bitset<MaxN> u,sl,sr;

int pairup(int nod)
{
	if( u[nod] )
		return 0;
	u[nod] = 1;
	vector<int>::iterator it;
	for( it = G[nod].begin() ; it != G[nod].end() ; ++it ) 
		if( !rt[*it] )
			{
				lt[nod] = *it;
				rt[*it] = nod;
				sr[nod] = 1;
				return 1;
			}
	for( it = G[nod].begin() ; it != G[nod].end() ; ++it )
		if( pairup(rt[*it]) )
			{
				lt[nod] = *it;
				rt[*it] = nod;
				sr[nod] = 1;
				return 1;
			}
	return 0;
}

void solve(int nod)
{
	vector<int>::iterator it;
	for( it = G[nod].begin() ; it != G[nod].end() ; ++it )
		if( !sl[*it] )
			{
				sl[*it] = 1;
				sr[rt[*it]] = 0;
				solve(rt[*it]);
			}
}

int main()
{
	freopen( InFile , "r" , stdin );
	freopen( OutFile , "w" , stdout );
	scanf("%d%d" , &N , &M );
	G.resize(N+1);
	int i,x,y;
	for( i = 0 ; i < M ; i++)
		{
			scanf("%d%d" , &x , &y );
			G[x].push_back(y);
		}
	for( i = 1 , cnt = 0 ; i <= N ; i++ )
		if( !pairup(i) )
			{
				u.reset();
				cnt += pairup(i);
			}
			else
			++cnt;
	for( i = 1 ; i <= N ; i++ )
		if( !sr[i] )
			solve(i);
	printf("%d\n" , 2*N-cnt);
	for( i = 1 ; i <= N ; i++ )
		{
			if( sl[i] && sr[i] )
				{
					printf("0\n");
					continue;
				}
			if( sl[i] && !sr[i] )
				{
					printf("1\n");
					continue;
				}
			if( !sl[i] && sr[i] )
				{
					printf("2\n");
					continue;
				}
			if( !sl[i] && !sr[i] )
				{
					printf("3\n");
					continue;
				}
		}
	return 0;
}