#include <stdio.h>
#include <vector>
using namespace std;
#define NMAX 8200
#define FOR(i, v) for(vector<int>::iterator i = v.begin(); i != v.end(); i++)
vector <int> v[NMAX];
int r[NMAX], l[NMAX], s[NMAX], d[NMAX], u[NMAX];
int n, m;
int pairup(int x){
	if(u[x]) return 0;
	u[x] = 1;
	
	FOR(i,v[x])
		if(!r[*i]){
			r[*i] = x;
			l[x] = *i;
			return 1;
		}
	FOR(i,v[x])
		if(pairup(r[*i])){
			r[*i] = x;
			l[x] = *i;
			return 1;
		}
	return 0;
}
void suport(int x){
	FOR(i, v[x])
		if(!d[*i]){
			s[r[*i]]=0;
			d[*i]=1;
			suport(r[*i]);
		}
}
int main(){
	freopen("felinare.in","r",stdin);
	freopen("felinare.out","w",stdout);
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= m; ++i){
		int x, y;
		scanf("%d %d", &x, &y);
		v[x].push_back(y);
	}
	int ok = 1;
	while(ok){
		ok = 0;
		memset(u, 0, sizeof(u));
		for(int i = 1; i <= n; ++i)
			if(!l[i]) ok |= pairup(i);
	}
	
	int cuplaj = 0;
	for(int i = 1; i <= n; ++i)
		cuplaj += (l[i] > 0);
	printf("%d\n", 2*n-cuplaj);
	
	for(int i = 1; i <= n; ++i)
		s[i] = (l[i] > 0);
	
	for(int i =1; i <= n; ++i)
		if(!l[i]) suport(i);
	for(int i = 1; i <= n; ++i)
		if(s[i] && d[i]) printf("0\n");
		else if(s[i]) printf("2\n");
		else if(d[i])printf("1\n");
		else printf("3\n");
		
	return 0;
}