#include <cstdio>
#include <cstring>
#include <vector>

#define nmax 8195

using namespace std;

int n, m, a [nmax], b [nmax];
bool v [nmax], s [2*nmax];
vector <int> g [nmax];


bool pairup (int k)
{
	if (v [k] == true) return false;
	v [k]=true;
	int i;
	for (i=0; i != g [k].size (); ++i)
		if (a [g [k] [i]] == 0)
		{
			a [g [k] [i]]=k;
			b [k]=g [k] [i];
			return true;
		}
	for (i=0; i != g [k].size (); ++i)
		if (v [a [g [k] [i]]] == false && pairup (a [g [k] [i]]))
		{
			a [g [k] [i]]=k;
			b [k]=g [k] [i];
			return true;
		}
	return false;
}

int cuplaj ()
{
	bool ok=true;
	int i, r=0;
	while (ok)
	{
		ok=false;
		memset (v, 0, sizeof (v));
		for (i=1; i <= n; ++i) 
			if (b [i] == 0 && pairup (i)) ok=true;
	}
	for (i=1; i <= n; ++i)
		if (a [i]) ++r;
	return r;
}

void calculeaza (int k)
{
	int i;
	for (i=0; i != g [k].size (); ++i)
		if (s [g [k] [i]+n] == false)
		{
			s [g [k] [i]+n]=true;
			s [a [g [k] [i]]]=false;
			calculeaza (a [g [k] [i]]);
		}
}

void suport ()
{
	int i;
	for (i=1; i <= n; ++i)
		if (b [i]) s [i]=true;
	for (i=1; i <= n; ++i)
		if (s [i] == false) calculeaza (i);
}

void print ()
{
	int i;
	for (i=1; i <= n; ++i)
	{
		if (s [i] == true && s [i+n] == true) printf ("0\n");
		if (s [i] == false && s [i+n] == true) printf ("1\n");
		if (s [i] == true && s [i+n] == false) printf ("2\n");
		if (s [i] == false && s [i+n] == false) printf ("3\n");
	}
}

int main ()
{
	freopen ("felinare.in", "r", stdin);
	freopen ("felinare.out", "w", stdout);
	int i, x, y;
	scanf ("%d%d", &n, &m);
	for (i=1; i <= m; ++i)
	{
		scanf ("%d%d", &x, &y);
		g [x].push_back (y);
	}
	printf ("%d\n", 2*n-cuplaj ());
	suport ();
	print ();
	return 0;
}