#include<stdio.h>
#include<stdlib.h>
#define infile "felinare.in"
#define outfile "felinare.out"
#define nmax 10013
struct nod
{
	int *v; //vectorul cu vecinii
	int n; //numarul de vecini
	int al; //memoria alocata
} no[nmax]; //informatiile nodurilor
int st[nmax]; //st[i]=cu cine e cuplat nodul i din stanga
int dr[nmax]; //dr[i]=cu cine e cuplat nodul i din dreapta
char viz[nmax]; //vizite ;p
int n; //numarul de noduri
int cuplaj; //valoarea cuplajului

inline void push(int x, int y)
{
	if(!no[x].al) no[x].al=4, no[x].v=(int *) malloc(no[x].al*sizeof(int));
	else if(no[x].n+1==no[x].al) no[x].al<<=1, no[x].v=(int *) realloc(no[x].v, no[x].al*(sizeof(int)));
	no[x].v[++no[x].n]=y;
}

void read()
{
	int a,b,m;
	scanf("%d %d\n",&n,&m);
	while(m--)
	{
		scanf("%d %d\n",&a,&b);
		push(a,b);
	}
}

int pairup(int x)
{
	if(viz[x]) return 0;
	viz[x]=1;
	int i;
	for(i=1;i<=no[x].n;i++)
		if(!dr[no[x].v[i]] || pairup(dr[no[x].v[i]]))
		{
			st[x]=no[x].v[i];
			dr[no[x].v[i]]=x;
			return 1;
		}
	return 0;
}

void solve()
{
	int i,ok=1;
	
	//facem cuplajul
	while(ok)
	{
		ok=0;
		for(i=1;i<=n;i++) viz[i]=0;
		for(i=1;i<=n;i++)
			if(!st[i] && pairup(i))
				ok=1, cuplaj++;
	}
}

void write()
{
	int i;
	printf("%d\n",(n<<1)-cuplaj);
	for(i=1;i<=n;i++)
		if(!st[i]) printf("%d\n",3);
		else printf("%d\n",1);
}

int main()
{
	freopen(infile,"r",stdin);
	freopen(outfile,"w",stdout);
	
	read();
	solve();
	write();
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}