#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],w[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;
		return true;
		}

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

}

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

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

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

for(i = 0 ;i< N ; i++)
	if(!w[r[nod][i]])
	if(Pair1(d[r[nod][i]]))
		{s[nod] = r[nod][i];
		d[r[nod][i] ] = nod;
		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 solve(){
bool ok = true;
int i;
//primul cuplaj;

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])
		w[i] = true;
memset(s,0,sizeof(s));
memset(d,0,sizeof(d));
while(ok){
	ok = false;
	memset(viz,0,sizeof(viz));
	for( i =1  ; i<= n ; i++)
		if(!s[i] && Pair2(i))
			{sol++;
			ok =true;}
	}

}

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

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

for(i = 1 ; i <= n ; i++)
	if(w[i] && s[i])
		printf("0\n");
	else
	if(w[i])
		printf("2\n");
	else
	if(s[i])
		printf("1\n");
	else
		printf("3\n");
}

int main(){

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

return 0;}