#include <cstdio>
#include <vector>
using namespace std;
#define nmax 8200

vector <int> g[nmax];
int n, m, d, u[2*nmax], c[nmax], p[nmax];

int pairup (int nod)
{
	if (u[nod]==d) return 0;
	int i, v;
	u[nod]=d;
	for (i=0; i<g[nod].size(); i++)
	{
		v=g[nod][i];
		if (!p[v] || pairup(p[v]))
		{
			c[nod]=v;
			p[v]=nod;
			return 1;
		}
	}
	return 0;
}

void support (int nod)
{
	int i, v;
	for (i=0; i<g[nod].size(); i++) 
	{
		v=g[nod][i];
		if (!u[v+n])
		{
			u[v+n]=1;
			u[c[v]]=0;
			support(c[v]);
		}
	}
}

int main()
{
	freopen("felinare.in","r",stdin);
	freopen("felinare.out","w",stdout);
	scanf("%d %d", &n, &m);
	int i, x, y, sum, last;
	for (i=1; i<=m; i++)
	{
		scanf("%d %d", &x, &y);
		g[x].push_back(y);
	}
	last=-1;
	sum=0;
	while (last!=sum)
	{
		last=sum;
		d++;
		for (i=1; i<=n; i++)
			if (!c[i]) sum+=pairup(i);
	}
	for (i=1; i<=n; i++) u[i]=0;
	printf("%d\n",2*n-sum);
	for (i=1; i<=n; i++)
		if (c[i]) u[i]=1;
	for (i=1; i<=n; i++)
		if (!c[i]) support(i);
	for (i=1; i<=n; i++)
	{
		x=3;
		if (u[i]) x--;
		if (u[n+i]) x-=2;
		printf("%d\n",x);
	}
}