#include <cstdio>
#include <vector>

using namespace std;

#define sz size()
#define pb push_back

#define Nmax 9000

int n, m;
vector<int> vec[Nmax];
int v[Nmax];
int cur, viz[Nmax];
int dest[Nmax], cuplat[Nmax];
char mark[2*Nmax];

void readdata()
{
	freopen("felinare.in", "r", stdin);
	freopen("felinare.out", "w", stdout);
	
	int m, a, b;
	
	for (scanf("%d %d", &n, &m); m; --m)
	{
		scanf("%d %d", &a, &b);
		vec[a].pb(b);
	}
	
}

int cupleaza(int k)
{
	int i, nod;
	
	if (viz[k] == cur) return 0;
	
	viz[k] = cur;
	
	for (i = 0; i < vec[k].sz; ++i)
	{
		nod = vec[k][i];
		if (dest[nod] == 0 || cupleaza(dest[nod]))
		{
			dest[nod] = k;
			cuplat[k] = nod;
			return 1;
		}
	}
	return 0;
}

void rezolva(int k)
{
	int i, nod;
	
	for (i = 0; i < vec[k].sz; ++i)
	{
		nod = vec[k][i];
		if (!mark[n+nod])
		{
			mark[n+nod] = 1;
			mark[ dest[nod] ] = 0;
			rezolva(dest[nod]);
		}
	}
}

void solve()
{
	int i, rez = 0;
	
	for (i = 1; i <= n; ++i)
	{
		cur = i;
		rez += cupleaza(i);
	}
	printf("%d\n", 2*n-rez);
	
	for (i = 1; i <= n; ++i)
		if (cuplat[i]) mark[i] = 1;
		
	for (i = 1; i <= n; ++i)
		if (!cuplat[i]) rezolva(i);
		
	for (i = 1; i <= n; ++i)
	{
		v[i] = 3;
		if (mark[i]) v[i] -= 1;
		if (mark[n+i]) v[i] -= 2;
	}
	
	for (i = 1; i <= n; ++i)
		printf("%d\n", v[i]);
}

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