#include<stdio.h>
#include<vector>
#include<string.h>
using namespace std;

vector<int> l[8200],r[8200];

int s[8200],d[8200],i,j,k,m,n,sol;

bool viz[8200],Sl[8200],Sr[8200];

bool Pair1(int nod){
if(viz[nod])return false;
viz[nod] = true;

int N,i;
N = l[nod].size();

for(i = 0 ; i < N ; i++)
	if(!d[l[nod][i]])
		{s[nod] = l[nod][i];
		d[l[nod][i] ] = nod;
		Sl[nod] = 1;
		return true;
		}

for(i = 0 ;i< N ; i++)
	if(Pair1(d[l[nod][i]]))
		{s[nod] = l[nod][i];
		d[l[nod][i] ] = nod;
		Sl[nod] = 1;
		return true;
		}
return false;

}


void citire(){
freopen("felinare.in","r",stdin);
scanf("%d %d",&n,&m);
int i,a,b;
for(i = 1 ; i <= m ; i++)
	{scanf("%d %d",&a,&b);
	l[a].push_back(b);
	r[b].push_back(a);
	}

}

void suport(int nod){
int N,X,i;
N = l[nod].size();
for(i  = 0 ; i< N;i++){
	X  = l[nod][i];
	if(!Sr[X])
		{Sr[X] = true;
		Sl[s[X]] = 0;
		suport(s[X]);
		}
	}
}
void solve(){
bool ok = true;
int i;


while(ok){
	ok = false;
	memset(viz,0,sizeof(viz));
	for( i =1  ; i<= n ; i++)
		if(!s[i] && Pair1(i))
			{sol++;
			ok =true;}
	}
for(i = 1 ;  i<= n;  i++)
	if(!s[i])
		suport(i);
}

void afisare(){
freopen("felinare.out","w",stdout);

printf("%d\n",2*n - sol);

for(i = 1 ; i <= n ; i++){
		if(Sl[i] && Sr[i]) printf("0\n");
        if(!Sl[i] && Sr[i]) printf("1\n");
        if(Sl[i] && !Sr[i]) printf("2\n");
        if(!Sl[i] && !Sr[i]) printf("3\n");
	}

}

int main(){

citire();
solve();
afisare();

return 0;}