#include <stdio.h>
#include <string.h>
#include <vector>
#define pb push_back
#define NMAX 8201
#define LMAX 16501
using namespace std;
int n,m,st[NMAX],dr[NMAX],rez,answer[NMAX];
vector <int> A[NMAX];
char marc[NMAX],viz[LMAX];
void read()
{
	scanf("%d%d",&n,&m);
	int i,x,y;
	for (i=1; i<=m; i++)
	{
		scanf("%d%d",&x,&y);
		A[x].pb(y);
	}
}
int pairup(int nod)
{
	marc[nod]=1;
	int i,vec;
	for (i=0; i<A[nod].size(); i++)
	{
		vec=A[nod][i];
		if (!dr[vec])
		{
			st[nod]=vec;
			dr[vec]=nod;
			return 1;
		}
	}
	for (i=0; i<A[nod].size(); i++)
	{
		vec=A[nod][i];
		if (!marc[dr[vec]] && pairup(dr[vec]))
		{
			st[nod]=vec;
			dr[vec]=nod;
			return 1;
		}
	}
	return 0;
}
void cuplaj()
{
	int i,ok=1;
	while (ok)
	{
		memset(marc,0,sizeof(marc));
		ok=0;
		for (i=1; i<=n; i++)
			if (!st[i])
			{
				if (pairup(i))
					rez++, ok=1;
			}
	}
}
void solve_problem(int nod)
{
	if (viz[nod])
		return ;
	int i,vec;
	for (i=0; i<A[nod].size(); i++)
	{
		vec=A[nod][i];
		if (!viz[vec+n])
		{
			viz[vec+n]=1;
			viz[dr[vec]]=0;
			solve_problem(dr[vec]);
		}
	}
}
void solve()
{
	int i;
	for (i=1; i<=n; i++)
		if (st[i])
			viz[i]=1;
	for (i=1; i<=n; i++)
		if (!st[i])
			solve_problem(i);
	for (i=1; i<=n; i++)
	{
		if (viz[i])
			answer[i]++;
		if (viz[i+n])
			answer[i]+=2;
	}
	for (i=1; i<=n; i++)
		printf("%d\n",3-answer[i]);
}
int main()
{
	freopen("felinare.in","r",stdin);
	freopen("felinare.out","w",stdout);
	read();
	cuplaj();
	printf("%d\n",2*n-rez);
	solve();
	return 0;
}