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

int n, m;
int cuplaj;
int L[DIM], R[DIM];
bool v[DIM];
vector<int> G[DIM];
int sl[DIM], sr[DIM];

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

int main()
{
	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();
	
	bool am_cuplaj;
	do
	{
		am_cuplaj = false;
		for (int i = 1; i <= n; ++i)
			if (!L[i] && Cupleaza(i))
			{
				cuplaj++;
				am_cuplaj = true;
			}
	}while(am_cuplaj);
	
	for (int i = 1; i <= n; ++i)
		if (L[i]) sl[i] = 1;
	for (int i = 1; i <= n; ++i)
		if (!sl[i]) PairUp(i);
	
	ofstream fout("felinare.out");
	fout << 2*n - 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();
	return 0;
}


bool Cupleaza(int nod)
{
	if (v[nod]) return false;
	v[nod] = 1;
	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]);
		}
}