#include <stdio.h>
#include <vector>
#include <algorithm>

#define nmax 16400
#define pb push_back
#define sz size()

using namespace std;

vector <int> e[nmax];
char v[nmax];
int i,n,m,x1,y1,tot,c[nmax];

int cupl(int x) {
	if(v[x] == 1) return 0;
	v[x] = 1;
	for(int i = 0; i < (int)e[x].sz; i++)
		if(!c[e[x][i]]) {
			c[x] = e[x][i];
			c[e[x][i]] = x;
			return 1;
		}
	for(int i = 0; i < (int)e[x].sz; i++)
		if(cupl(c[e[x][i]])) {
			c[x] = e[x][i];
			c[e[x][i]] = x;
			return 1;
		}
	return 0;
}

void calc(int x) {
	for(int i = 0; i < (int)e[x].sz; i++) 
		if(!v[e[x][i]]) {
			v[e[x][i]] = 1;
			v[c[e[x][i]]] = 0;
			calc(c[e[x][i]]);
		}
}

int main() {
	freopen("felinare.in","r",stdin);
	freopen("felinare.out","w",stdout);

	scanf("%d%d",&n,&m);
	for(i = 1; i <= m; i++) {
		scanf("%d%d",&x1,&y1);
		e[x1].pb(y1 + n);
		e[y1 + n].pb(x1);
	}

	for(i = 1; i <= n; i++) 
		if(!c[i] && !cupl(i)) {
			memset(v,0,sizeof(v));
			cupl(i);
		}

	memset(v,0,sizeof(v));

	for(i = 1; i <= n; i++) if(c[i]) v[i] = 1; 
	for(i = 1; i <= n; i++) if(!c[i]) calc(i);

	tot = 2 * n;
	for(i = 1; i <= 2 * n; i++) tot -= v[i];

	printf("%d\n",tot);
	for(i = 1; i <= n; i++) 
		if(!v[i] && !v[i + n]) printf("3\n");
		else if(!v[i] && v[i + n]) printf("1\n");
		else if(v[i] && !v[i + n]) printf("2\n");
		else printf("0\n");

	return 0;
}