#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const char iname[] = "felinare.in";
const char oname[] = "felinare.out";

ifstream fin(iname);
ofstream fout(oname);

int n, m, e, i, x, y, am_cuplat, viz[10050], c;
vector<int> Gr[10050];
int R[10050], L[10050];
int SL[10050], SR[10050];

int pair_up(int nod)
{	
	if(viz[nod] == 1)
		return 0;
	viz[nod] = 1;
	for(vector<int>::iterator it = Gr[nod].begin(); it != Gr[nod].end(); ++ it)
	{
		if(R[*it] == 0)
		{
			L[nod] = *it;
			R[*it] = nod;
			return 1;
		}
	}
	for(vector<int>::iterator it = Gr[nod].begin(); it != Gr[nod].end(); ++ it)
	{
		if(pair_up(R[*it]))
		{
			L[nod] = *it;
			R[*it] = nod;
			return 1;
		}
	}
	return 0;
}
		
void suport(int nod)
{
	for(vector<int>::iterator it = Gr[nod].begin(); it != Gr[nod].end(); ++ it)
	{
		if(SR[*it] == 0)
		{
			SR[*it] = 1;
			SL[R[*it]] = 0;
			suport(R[*it]);
		}
	}
}

int main()
{
	fin >> n >> m;
	for(i = 1; i <= m; i ++)
	{
		fin >> x >> y;
		Gr[x].push_back(y);
	}
	
	am_cuplat = 1;
	while(am_cuplat)
	{	
		am_cuplat = 0;
		for(i = 1; i <= max(n, m); i ++)
			viz[i] = 0;
		for(i = 1; i <= n; i ++)
			if(L[i] == 0)
				if(pair_up(i) == 1)
					++c, am_cuplat = 1;
	}
	fout << 2 * n - c << "\n";
	for(i = 1; i <= n; i ++)
		if(L[i])
			SL[i] = 1;
	
	for(i = 1; i <= n; i ++)
		if(SL[i] == 0)
			suport(i);
	
	for(i = 1; i <= n; i ++)
	{
		if(SL[i] && SR[i]) fout << "0\n";
		if(SL[i] && !SR[i]) fout << "2\n";
		if(!SL[i] && SR[i]) fout << "1\n";
		if(!SL[i] && !SR[i]) fout << "3\n";
	}
	return 0;
}