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

int n, m, i, x, y, p[MAX], state, couple;
bool viz[MAX], viz2[MAX], stop;
vector<int> l[MAX];

int matching(int n){
	if(viz[n])
		return 0;
	viz[n] = 1;
	for(int i = 0; i < l[n].size(); i++)
		if(!p[l[n][i]] || matching(p[l[n][i]])){
			viz2[n] = 1;
			p[n] = l[n][i];
			p[l[n][i]] = n;
			return 1;
		}
	return 0;
}

void f(int n){
	for(int i = 0; i < l[n].size(); i++)
		if(!viz2[l[n][i]]){
			viz2[l[n][i]] = 1;
			viz2[p[l[n][i]]] = 0;
			f(p[l[n][i]]);
		}
}

int main(){
	freopen("felinare.in", "r", stdin);
	freopen("felinare.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for(i = 0; i < m; i++){
		scanf("%d%d", &x, &y);
		l[x].push_back(y + n);
	}

	stop = 1;
	while(stop){
		stop = 0;
		memset(viz, 0, n + 1);
		for(i = 1; i <= n; i++)
			if(!p[i])
				stop |= matching(i);
	}

	for(i = 1; i <= n; i++)
		if(p[i])
			couple++;

	for(i = 1; i <= n; i++)
		if(!p[i])
			f(i);

	printf("%d\n", 2 * n - couple);
	for(i = 1; i <= n; i++){
		state = 0;
		if(!viz2[i])
			state++;
		if(!viz2[i + n])
			state += 2;
		printf("%d\n", state);
	}
	return 0;
}