#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
char viz_st[nmax]; //ca sa stim daca il stingem
char viz_dr[nmax]; //ca sa stim daca il stingem
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 compute(int x)
{
	int i;
	for(i=1;i<=no[x].n;i++)
		if(!viz_dr[no[x].v[i]])
		{
			viz_dr[no[x].v[i]]=1;
			viz_st[dr[no[x].v[i]]]=0;
			compute(dr[no[x].v[i]]);
		}
}

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++;
	}
	
	//stabilim care felinare le stingem
	for(i=1;i<=n;i++)
		if(st[i])
			viz_st[i]=1;
	for(i=1;i<=n;i++)
		if(!st[i])
			compute(i);
}

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

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