#include <stdio.h>
#include <vector>
#define Nmax 8200
#define pb push_back

using namespace std;

vector< int > v[Nmax];
int use[Nmax],st[Nmax],dr[Nmax],din_st[Nmax],din_dr[Nmax];
int n,m,muchii,ok;

int cupleaza(int i){
	vector< int >:: iterator it;
	if( use[i] ) return 0;
	use[i]=1;
	
	for(it=v[i].begin(); it!=v[i].end(); ++it)
		if( !st[*it] || cupleaza( st[*it] ) ){
			dr[i] = *it;
			st[*it]=i;
			ok=1; return 1;
		}
	return 0;
}

void work( int i ){
	vector< int >:: iterator it;
	
	for(it=v[i].begin(); it!=v[i].end(); ++it)
		if( ! din_dr[*it] ){
			din_dr[*it]=1;
			din_st[st[*it]]=0;
			work(st[*it]);
		}
}	

int main(){
	int i,x,y;
	freopen("felinare.in","r",stdin);
	freopen("felinare.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;++i){
		scanf("%d%d",&x,&y);
		v[x].pb(y);
	}
	
	for(ok=1; ok ; ){
		ok=0; memset(use,0,sizeof(use));
		
		for(i=1;i<=n;++i)
			if( !dr[i] )
				muchii += cupleaza(i);
	}
	
	for(i=1;i<=n;++i)
		if( dr[i] ) din_st[i]=1;
	for(i=1;i<=n;++i)
		if( !dr[i] ) work( i ); 
	
	printf("%d\n",2*n-muchii);
	for(i=1;i<=n;++i)
		if( din_st[i] && din_dr[i] ) printf("%d\n",0);
		else if( din_st[i] ) printf("%d\n",2);
		else if( din_dr[i] ) printf("%d\n",1);
		else printf("%d\n",3);
	fclose(stdin); fclose(stdout);
	return 0;
}