#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<deque>
#include<queue>
#include<set>
#include<vector>
using namespace std;

const char IN[] = {"felinare.in"};
const char OUT[] = {"felinare.out"};
const int INF = 1000000005;
const double PI  = 3.14159265;
const int NMAX = 8205;

#define II inline
#define LL long long
#define PII pair<int, int>
#define PDD pair<double, double>
#define fs first
#define ss second
#define mp make_pair
#define pb push_back
#define FOR(i, a, b) 	for(int i = a ; i <= b ; i++)
#define IFOR(i, a, b) 	for(int i = a ; i >= b ; i--)
#define FORIT(it, V) 	for(vector<int> :: iterator it = V.begin() ; it != V.end() ; it++)
#define all(a) a, a + 

int N, M;
vector<int> Graf[NMAX];
int u[NMAX], r[NMAX], l[NMAX];
int CPL;
int sol[NMAX][2];

void citi()
{
	scanf("%d%d", &N, &M);
	FOR(i, 1, M)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		Graf[x].pb(y);
	}
}

bool leaga(int nod)
{
	if(u[nod])	return 0;
	u[nod] = 1;
	FORIT(it, Graf[nod])
		if(!l[*it])
		{
			r[nod] = *it;
			l[*it] = nod;
			return 1;
		}
	FORIT(it, Graf[nod])
		if(leaga(l[*it]))
		{
			r[nod] = *it;
			l[*it] = nod;
			return 1;
		}
	return 0;
}

void cuplaj()
{
	bool sol = 1;
	while(sol)
	{
		sol = 0;
		fill(u + 1, u + N + 1, 0);
		FOR(i, 1, N)
			if(!r[i])
				sol |= leaga(i);
	}
}

void compune(int nod)
{
	FORIT(it, Graf[nod])
		if(!sol[*it][1])
		{
			sol[*it][1] = 1;
			sol[l[*it]][0] = 0;
			compune(l[*it]);
		}
}

void suport_minim()
{
	FOR(i, 1, N)
		if(r[i])
			sol[i][0] = 1;
	FOR(i, 1, N)
		if(!sol[i][0])
			compune(i);
}

void scrie()
{
	FOR(i, 1, N)	if(r[i])	CPL++;
	printf("%d\n", 2 * N - CPL);
	FOR(i, 1, N)
	{
		if(sol[i][0] && sol[i][1])
			printf("0\n");
		if(!sol[i][0] && sol[i][1])
			printf("1\n");
		if(sol[i][0] && !sol[i][1])
			printf("2\n");
		if(!sol[i][0] && !sol[i][1])
			printf("3\n");
	}
}

int main()
{
	freopen(IN, "r", stdin);
	freopen(OUT, "w", stdout);
	citi();
	cuplaj();
	suport_minim();
	scrie();
	return 0;
}