#include<fstream>
#include<vector>
#include<algorithm>
#include<string.h>
#define dim 8200
using namespace std;


ifstream f("felinare.in");
ofstream g("felinare.out");
int w[dim],n,m,i,nr,x,y,l[dim],r[dim],change,sl[dim],sr[dim];
vector<int>G[dim];
int pairup (int x) {
	
	if(w[x])
		return 0;
	w[x]=1;
	
	for(int i=0;i<G[x].size();++i){
		
		if(!r[G[x][i]]){
			
			r[G[x][i]]=x;
			l[x]=G[x][i];
			return 1;
		}
	}
	for(int i=0;i<G[x].size();++i){
		
		if(pairup(r[G[x][i]])){
			r[G[x][i]]=x;
			l[x]=G[x][i];
			return 1;
		}
		
	}
	return 0;
}
int suport_minim( int n ) {
	
	for(int i=0 ;i<G[n].size();++i){
		int fiu = G[n][i];
		if(!sr[fiu]){
			sr[fiu]=1;
			sl[r[fiu]]=0;
			suport_minim(r[fiu]);
		}
	}
}
int main () {
	
	f>>n>>m;
	
	
	for(i=1;i<=m;i++){
		f>>x>>y;
		G[x].push_back(y);
	}
	
	
	change =1;
	do{
		
		change =0;
		memset(w,0,sizeof(w));
		
		for(i=1;i<=n;i++)
			if(!l[i]){
				change|=pairup(i);
			}
	}while(change);
	for(i=1;i<=n;i++)
		if(l[i])
			nr++;
	g<<2*n-nr<<"\n";
	
	for(i=1;i<=n;i++)
		if(l[i])
			sl[i]=1;
	for(i=1;i<=n;i++)
		if(l[i]==0)
			suport_minim(i);
	for(i=1;i<=n;i++){
		if(sl[i] && sr[i])
			g<<0<<"\n";
		if(sl[i] && !sr[i])
			g<<2<<"\n";
		if(!sl[i] && sr[i])
			g<<1<<"\n";
		if(!sl[i] && !sr[i])
			g<<3<<"\n";
		
	}
	return 0;
}