#include <fstream>
#include <cstdlib>
#include <cstring>
#include <vector>

#define nextNode g[node][i]

using namespace std;

ifstream in("felinare.in");
ofstream out("felinare.out");

const int N = 8192;

int n;
int st[N];
int dr[N];

bool viz[N];
bool stMark[N];
bool drMark[N];

vector <int> g[N];

void Read()
{
	int m;

	in >> n >> m;
	while (m--)
	{
		int a, b;

		in >> a >> b;
		g[a].push_back(b);
	}
}

bool Match(int node)
{
	if (viz[node])
		return false;
	viz[node] = true;

	for (int i = 0; i < g[node].size(); ++i)
		if (!st[nextNode])
		{
			st[nextNode] = node;
			dr[node] = nextNode;

			return true;
		}

	for (int i = 0; i < g[node].size(); ++i)
		if (Match(st[nextNode]))
		{
			st[nextNode] = node;
			dr[node] = nextNode;

			return true;
		}

	return false;
}

void Solve()
{
	bool still = true;

	while (still)
	{
		still = false;
		memset(viz, 0, sizeof(viz));

		for (int i = 1; i <= n; ++i)
			if (!dr[i] && Match(i))
				still = true;
	}
}

void InitialMarks()
{
	for (int i = 1; i <= n; ++i)
		if (dr[i])
			stMark[i] = true;
}

void TryMark(int node)
{
	for (int i = 0; i < g[node].size(); ++i)
		if (drMark[nextNode])
		{
			stMark[st[nextNode]] = false;
			drMark[nextNode] = true;
			TryMark(st[nextNode]);
		}
}

void Vertex()
{
	InitialMarks();

	for (int i = 1; i <= n; ++i)
		if(!stMark[i])
			TryMark(i);
}

inline int Result(int node)
{
	if (stMark[node] && drMark[node])
		return 0;
	if (drMark[node])
		return 1;
	if (stMark[node])
		return 2;
	return 3;
}

void Print()
{
	int result = 0;

	for (int i = 1; i <= n; ++i)
	{
		if (stMark[i])
			++result;
		if (drMark[i])
			++result;
	}

	out << 2*n - result << "\n";

	for (int i = 1; i <= n; ++i)
		out << Result(i) << "\n";
}

int main()
{
	Read();
	Solve();
	Vertex();
	Print();

	return 0;
}