#include <fstream>
#include <vector>
#define DIM 10000
using namespace std;

int n, m;
int s[DIM];
int L[DIM], R[DIM];
int sL[DIM], sR[DIM];
long cuplaj;
vector<int> G[DIM];

void Read();
bool Cupleaza(int);
void Write();
void PairUp(int);

int main()
{
	Read();
	bool am_cuplaj;
	do
	{
		am_cuplaj = false;
		memset(s, false, sizeof(s));
		for (int i = 1; i <= n; ++i)
			if (!L[i] && Cupleaza(i)) // daca nu e cuplat sau gasesc lant
			{
				am_cuplaj = true;
				cuplaj++;
			}
	}while (am_cuplaj);
	
	for (int i = 1; i <= n; ++i)
		if (L[i]) sL[i] = 1;
	for (int i = 1; i <= n; ++i)
		if (!L[i]) PairUp(i);
	Write();
	return 0;
}

bool Cupleaza(int nod)
{
	if (s[nod]) return false;
	s[nod] = true;
	for (vector<int>::iterator it = G[nod].begin(); it != G[nod].end(); ++it)
		if (!R[*it] || Cupleaza(R[*it]) )
		{
			L[nod] = *it;
			R[*it] = nod;
			return true;
		}
	return false;
}

void PairUp(int nod)
{
	for (vector<int>::iterator it = G[nod].begin(); it != G[nod].end(); ++it)
		if (!sR[*it])
		{
			sR[*it] = 1;
			sL[R[*it]] = 0;
			PairUp(R[*it]);
		}
}

void Read()
{
	ifstream fin("felinare.in");
	fin >> n >> m;
	int x, y;
	for (int i = 1; i <= m; ++i)
	{
		fin >> x >> y;
		G[x].push_back(y);
	}
	fin.close();
}

void Write()
{
	ofstream fout("felinare.out");
	fout << 2*n - cuplaj << '\n';
	//fout << cuplaj << '\n';
	for (int i = 1; i <= n; ++i)
	{
		if (sL[i] && sR[i]) fout << '0' << '\n';
		if (!sL[i] && sR[i]) fout << '1' << '\n';
		if (sL[i] && !sR[i]) fout << '2' << '\n';
		if (!sL[i] && !sR[i]) fout << '3' << '\n';
	}
	fout.close();
}