#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#define NMAX 9000

using namespace std;

int a[NMAX][NMAX],viz[NMAX],l[NMAX],r[NMAX],st[NMAX],dr[NMAX];
int i,j,n,m,card;


int cupleaza(int i)
{
	int j;
	if(viz[i] == 1)
		return 0;
	viz[i] = 1;
	
	for(j=1;j<=n;j++)
		if(a[i][j])
			if(!r[j])
		{
			l[i] = j;
			r[j] = i;
			return 1;
		}
	for(j=1;j<=n;j++)
		if(a[i][j])
			if(cupleaza(r[j]))
			{
				l[i] = j;
				r[j] = i;
				return 1;
			}
	
	return 0;
}


void cupleaza2(int i)
{
	int j;
	
	for(j=1;j<=n;j++)
		if(a[i][j])
			if(!dr[j])
			{
				dr[j] = 1;
				st[r[j]] = 0;
			cupleaza2(r[j]);
			}
}
	

int main()
{
	int k,ok = 1;
	
	ifstream fin("felinare.in");
	ofstream fout("felinare.out");
	
	fin>>n>>m;
	
	for(k=1;k<=m;k++)
	{
		fin>>i>>j;
		a[i][j] = 1;
	}
	

	while(ok)
	{
		ok = 0;
		for(j=1;j<=n;j++)
			viz[j] = 0;
		for(i=1;i<=n;i++)
			if(!l[i] && cupleaza(i))
			{
				card++;
				ok = 1;
			}
	}
	
	for(i=1;i<=n;i++)
		if(l[i])
			st[i] = 1;
	for(i=1;i<=n;i++)
		if(!l[i])
			cupleaza2(i);
		
	fout<<2*n - card<<"\n";
	for(i=1;i<=n;i++)
	{
		if(st[i])
		{
			if(dr[i])
			fout<<3<<"\n";
		else
			fout<<1<<"\n";
		}
		
		if(!st[i])
		{
			if(!dr[i])
			fout<<0<<"\n";
		else
			fout<<2<<"\n";
		}
	}
	
return 0;
}