#include <fstream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

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

const int dim = 8200;

vector<int> graph[dim];

bool vis[dim];

int leftMatch[dim], rightMatch[dim];
bool leftSupport[dim], rightSupport[dim];

bool match(int node) {

	if (vis[node])
		return false;
	vis[node] = true;

	for (vector<int>::iterator adj = graph[node].begin(); adj != graph[node].end(); ++adj) {

		if (rightMatch[*adj] == 0) {
			leftMatch[node] = *adj;
			rightMatch[*adj] = node;
			return true;
		}

	}

	for (vector<int>::iterator adj = graph[node].begin(); adj != graph[node].end(); ++adj) {

		if (match(rightMatch[*adj])) {
			leftMatch[node] = *adj;
			rightMatch[*adj] = node;
			return true;
		}

	}

	return false;

}

void support(int node) {

	for (vector<int>::iterator adj = graph[node].begin(); adj != graph[node].end(); ++adj) {

		if (rightSupport[*adj])
			continue;

		rightSupport[*adj] = true;
		leftSupport[rightMatch[*adj]] = false;
		
		support(rightMatch[*adj]);

	}

}

int main() {

	int n, m;
	fin >> n >> m;

	for (int i = 1; i <= m; ++i) {

		int x, y;
		fin >> x >> y;

		graph[x].push_back(y);

	}

	bool ok;
	int maxMatchCount = 0;
	do {

		ok = false;
		memset(vis, false, sizeof vis);

		for (int i = 1; i <= n; ++i)
			if (leftMatch[i] == 0 && match(i))
				ok = true, ++maxMatchCount;

	} while (ok);

	for (int i = 1; i <= n; ++i)
		if (leftMatch[i] != 0)
			leftSupport[i] = true;

	for (int i = 1; i <= n; ++i)
		if (leftSupport[i] == false)
			support(i);

	fout << 2 * n - maxMatchCount << '\n';

	for (int i = 1; i <= n; ++i) {

		if (leftSupport[i] == 1 && rightSupport[i] == 1)
			fout << "0\n";
		else if (leftSupport[i] == 0 && rightSupport[i] == 1)
			fout << "1\n";
		else if (leftSupport[i] == 1 && rightSupport[i] == 0)
			fout << "2\n";
		else
			fout << "3\n";

	}

	return 0;

}

//Trust me, I'm the Doctor!