#include <fstream>
#include <vector>
#define MAX 8200

using namespace std;

int n, st[MAX], dr[MAX];
vector<vector<int> >g;
bool s[MAX];

bool cuplaj(int i)
{
	if (s[i]) return false;
	s[i] = 1;

	int j, p, x = g[i].size();
	for (p = 0; p < x; p++)
	{
		j = g[i][p];
		if (!dr[j])
		{
			st[i] = j;
			dr[j] = i;
			return true;
		}
	}
	for (p = 0; p < x; p++)
	{
		j = g[i][p];
		if (cuplaj(dr[j]))
		{
			st[i] = j;
			dr[j] = i;
			return true;
		}
	}
	return false;
}

int main()
{
	int ok, i, v1, v2, m;

	ifstream fin("felinare.in");
	fin >> n >> m;

	g.resize(n+1);
	for (; m; m--)
	{
		fin >> v1 >> v2;
		g[v1].push_back(n+v2);
	}
	fin.close();

	int nr = 0;

	for (ok = 1; ok; )
	{
		memset(s, 0, sizeof(s));
		for (ok = 0, i = 1; i <= n; i++)
			if (!st[i] && cuplaj(i))
			{
				nr++;
				ok = 1;
			}			
	}

	ofstream fout("felinare.out");
	fout << 2*n-nr << "\n";
	for (i = 1; i <= n; i++)
	{
		if (st[i] && dr[i]) fout << 0 << "\n";
		if (!st[i] && dr[i]) fout << 1 << "\n";
		if (st[i] && !dr[i]) fout << 2 << "\n";
		if (!st[i] && !dr[i]) fout << 3 << "\n";
	}
	fout.close();

	return 0;
}