#include <cstdio>
#include <cstdlib>
using namespace std;

const int NMAX = 9001;
const char Input[]="felinare.in";
const char Output[]="felinare.out";
const int erased = -1;

int status[NMAX],ideg[NMAX],odeg[NMAX],wasMax[NMAX];
int start[20005],final[20005];
int *b[NMAX],*t[NMAX];
int in,out,N,M,node;

inline void erase(int e1,int e2)
{
	ideg[e2]--;
	odeg[e1]--;
	int i;
	for(i=1; b[e1][i] != e2; i++);
	b[e1][i] = -1;
	for(i=1; t[e2][i] != e1; i++);
	t[e2][i] = -1;
}

inline int getMax()
{
	int i,max=0;
	for(i=1; i<=N; i++)
	{
	max=(ideg[i]>max)?out=0,in=1,node=i,ideg[i]:max;
	max=(odeg[i]>max)?in=0,out=1,node=i,odeg[i]:max;
	}
	return max;
}

void read()
{
	freopen (Input,"r",stdin);
	freopen (Output,"w",stdout);
	
	int i,e1,e2;
	
	scanf("%d %d",&N,&M);
	
	for(i=1; i<=N; i++)
		b[i]=(int*)malloc(sizeof(int)),t[i]=(int*)malloc(sizeof(int)),t[i][0] = b[i][0] = 0, status[i] = 3;

	for(i=1; i<=M; i++)
		{
			scanf("%d %d",&e1,&e2);
			start[i] = e1;
			final[i] = e2;
			ideg[e2]++;
			odeg[e1]++;
		}
	for(i=1; i<=N; i++)
		b[i] = new int[odeg[i]], t[i] = new int[ideg[i]], b[i][0] = t[i][0] = 0;
	for(i=1; i<=M; i++)
		b[start[i]][++b[start[i]][0]]=final[i], t[final[i]][++t[final[i]][0]]=start[i];
	//for(i=1; i<=N; i++)
		//printf("%d %d\n",ideg[i],odeg[i]);

}	

void solve()
{
	int i,nr=M,count=0,max;
	while(nr > 0)
	{
		in = 0;
		out = 0;
		node = 0;
		max = getMax();
		nr -= max;
		count++;
		if(in && status[node] == 3)
			status[node] = 1;
		if(in && status[node] == 2)
			status[node] = 0;
		if(out && status[node] == 3)
			status[node] = 2;
		if(out && status[node] == 1)
			status[node] = 0;
		
		if(out)
		for(i=1 ;i<=b[node][0] ; i++)
		if(b[node][i] != erased)
			erase(node,b[node][i]);
		
		if(in)
		for(i=1; i<=t[node][0] ; i++)
		if(t[node][i] != erased)
			erase(t[node][i],node);
	}
	printf("%d\n",(2*N - count));
	for(i=1; i<=N; i++)
		printf("%d\n",status[i]);
}

int main()
{
	read();
	solve();
	return 0;
}