#include <stdio.h>

bool a[8200][8200],l1[8200],l2[8200]; //false=bekapcsolva
int ki[8200],be[8200];
int n,m;


void beolvas() {
	FILE *f;
	int x,y,i;

	f= fopen("felinare.in","r");

	fscanf(f,"%d %d\n",&n,&m);
	for (i=1; i<=m; i++) {
		fscanf(f,"%d %d\n",&x,&y);
	    ki[x]++;
		be[y]++;
		a[x][y]=true;
	}
	fclose(f);
}

int main() {
	int db,le,p,max,i,e;

	beolvas();
	db=m; le=0;
	while (db>0) {
		max=0;p=0;le++;
		for (i=1; i<=n; i++)
			if ((ki[i]>max) || (be[i]>max)) {
			   p=i;
			   if (ki[i]>be[i]) 
				   max=ki[i];
			   else max=be[i];
			}
		db -= max;
		if (ki[p]==max){
			ki[p]=0;
			l1[p]=true;
			for (i=1; i<=n; i++)
				if (a[p,i]) be[i]--;

		}
		else {
			be[p]=0;
			l2[p]=true;
			for (i=1; i<=n; i++)
				if (a[i,p]) ki[i]--;
		}
	}
	FILE *f = fopen("felinare.out","w");
	fprintf(f,"%d\n",2*n-le);

	for (i=1; i<=n; i++){
		if (!l1[i] && !l2[i]) e=3;
		if (l1[i] && !l2[i]) e=2;
		if (!l1[i] && l2[i]) e=1;
		if (l1[i] && l2[i]) e=0;
	fprintf(f,"%d\n",e);
	}
	fclose(f);
}