#include <bitset>
#include <fstream>
#include <vector>
using namespace std;

ifstream fin("felinare.in");
ofstream fout("felinare.out");
const int kMax = 8200;
int n, m, matchSize, matchForw[kMax], matchBack[kMax];
vector<int> g[kMax];
bitset<kMax> vis;

bool foundMatchFor(int u)
{
	if (vis[u])
		return false;
	vis[u] = true;

	for (size_t i = 0; i < g[u].size(); ++i)
	{
		int v = g[u][i];
		if (!matchBack[v])
		{
			matchForw[u] = v;
			matchBack[v] = u;
			return true;
		}
	}

	for (size_t i = 0; i < g[u].size(); ++i)
	{
		int v = g[u][i];
		if (!vis[v] && foundMatchFor(matchBack[v]))
		{
			matchForw[u] = v;
			matchBack[v] = u;
			return true;
		}
	}
	return false;
}

void findMaximumMatch()
{
	bool changed;

	do
	{
		vis.reset();
		changed = false;
		
		for (int i = 1; i <= n; ++i)
			if (!matchForw[i])
				changed |= foundMatchFor(i);
	}
	while (changed);
}

int main()
{
	fin >> n >> m;
	for (int i = 0; i < m; ++i)
	{
		int u, v;	fin >> u >> v;
		g[u].push_back(v);
	}

	findMaximumMatch();
	

	for (int i = 1; i <= n; ++i)
		if (matchForw[i])
			++matchSize;

	fout << 2 * n - matchSize << '\n';
	for (int i = 1; i <= n; ++i)
	{
		if (matchForw[i])
			fout << "2\n";
		else
			fout << "3\n";
	}
	return 0;
}