#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#define nmx 8200

using namespace std;
ifstream fin("felinare.in");
ofstream fout("felinare.out");

int n,m,i,j,k,nr;
int l[nmx],r[nmx],u[nmx],z[nmx];
vector<int> ad[nmx];

int augment(int n)
{
	if(u[n])	return 0;
	u[n]=1;
	for(int i:ad[n])
		if(!r[i])
		{
			l[n]=i;
			r[i]=n;
			return 1;
		}
	for(int i:ad[n])
		if(augment(r[i]))
		{
			l[n]=i;
			r[i]=n;
			return 1;
		}
	return 0;
}

void paths(int n)
{
	if(u[n])	return;
	u[n]=1;
	
	for(int i:ad[n])
		if(l[n]!=i && z[i]==0)
		{
			z[i]=1;
			paths(r[i]);
		}
}

int main() {
	
	fin>>n>>m;
	for(i=1;i<=m;i++)
	{
		fin>>j>>k;
		ad[j].push_back(k);
	}
	
	for(int ok=1; ok;)
	{
		ok=0;
		memset(u, 0, sizeof(u));
		for(i=1;i<=n;i++)
			if(!l[i])
				ok|=augment(i);
	}
	
	memset(u, 0, sizeof(u));
	for(i=1;i<=n;i++)
	{
		if(l[i]==0)
			paths(i);
		else nr++;
	}
	
	for(i=1;i<=n;i++)
	{
		r[i]=0;
		if(u[i]==1)	r[i]++;
		if(z[i]==0)	r[i]+=2;
	}
	
	fout<<2*n-nr<<"\n";
	for(i=1;i<=n;i++)
		fout<<r[i]<<"\n";
}