#include<stdio.h>
#include<vector>

#define maxn 8205
#define pb push_back

using namespace std;

FILE*f=fopen("felinare.in","r");
FILE*g=fopen("felinare.out","w");

int n,m;
int L[maxn],R[maxn],viz[maxn],st[maxn],dr[maxn];
vector<int>G[maxn];

bool connect ( int nod ){
	if ( viz[nod] )	return 0;
	viz[nod] = 1;
	
	for ( vector<int>::iterator itt = G[nod].begin() ; itt != G[nod].end() ; ++itt ){
		int nodvcn = (*itt);
		if ( !R[nodvcn] ){
			L[nod] = nodvcn; R[nodvcn] = nod;
			return 1;
		}
	}
	
	for ( vector<int>::iterator itt = G[nod].begin() ; itt != G[nod].end() ; ++itt ){
		int nodvcn = (*itt);
		if ( connect(nodvcn) ){
			L[nod] = nodvcn; R[nodvcn] = nod;
			return 1;
		}
	}
	
	return 0;
}

inline int cuplaj () {
	int ok = 0;
	
	do{
		ok = 0;
		for ( int i = 1 ; i <= n ; ++i ){
			viz[i] = 0;
		}
		
		for ( int i = 1 ; i <= n ; ++i ){
			if ( !L[i] ){
				ok |= connect(i);
			}
		}
		
	}while(ok);
	
	int c = 0;
	for ( int i = 1 ; i <= n ; ++i ){
		if ( L[i] ){
			++c;
		}
	}
	
	return c;
}

void mark ( int nod ){
	
	for ( vector<int>::iterator itt = G[nod].begin() ; itt != G[nod].end() ; ++itt ){
		int nodvcn = (*itt);
		if ( !dr[nodvcn] ){
			dr[nodvcn] = 1;
			st[R[nodvcn]] = 0;
			mark(R[nodvcn]);
		}
	}
}

int main () {
	
	fscanf(f,"%d %d",&n,&m);
	int x,y;
	for ( int i = 1 ; i <= m ; ++i ){
		fscanf(f,"%d %d",&x,&y);
		G[x].pb(y);
	}
	
	int sol = (n<<1) - cuplaj();
	fprintf(g,"%d\n",sol);
	
	for ( int i = 1 ; i <= n ; ++i ){
		if ( L[i] ){
			st[i] = 1;
		}
	}
	
	for ( int i = 1 ; i <= n ; ++i ){
		if ( !st[i] ){
			mark(i);
		}
	}
	
	for ( int i = 1 ; i <= n ; ++i ){
		int now = 3;
		if ( st[i] ){
			now -= 1;
		}
		if ( dr[i] ){
			now -= 2;
		}
		fprintf(g,"%d\n",now);
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}