#include <bits/stdc++.h>

using namespace std;

const int NMAX = 10010;

int N, M;
int lt[NMAX], rt[NMAX];
bool vis[NMAX], minVertexLeft[NMAX], minVertexRight[NMAX];
vector<int> G[NMAX];

bool pairUp(int node) {
	if (vis[node])
		return 0;
	vis[node] = 1;
	for (const int &it: G[node])
		if (rt[it] == -1) {
			lt[node] = it;
			rt[it] = node;
			return 1;
		}
	for (const int &it: G[node])
		if (pairUp(rt[it])) {
			lt[node] = it;
			rt[it] = node;
			return 1;
		}
	return 0;
}

void buildMinVertexCover(int leftNode) {
	if (vis[leftNode])
		return;
	vis[leftNode] = 1;
	for (const int &it: G[leftNode]) {
		minVertexRight[it] = 1;
		if (rt[it] != -1)
			buildMinVertexCover(rt[it]);
	}
}

int main() {
	assert(freopen("felinare.in", "r", stdin));
	assert(freopen("felinare.out", "w", stdout));

	int i;
	cin >> N >> M;
	while (M--) {
		int x, y;
		cin >> x >> y;
		G[x].push_back(y);
	}

	memset(lt, -1, sizeof lt);
	memset(rt, -1, sizeof rt);
	bool change;
	int matchingSize = 0;
	do {
		change = 0;
		for (i = 1; i <= N; ++i)
			if (lt[i] == -1) {
				bool now = pairUp(i);
				change |= now;
				matchingSize += now;
			}
	} while (change);

	memset(vis, 0, sizeof vis);
	for (i = 1; i <= N; ++i)
		if (lt[i] == -1)
			buildMinVertexCover(i);
	for (i = 1; i <= N; ++i)
		if (lt[i] != -1 && !vis[i])
			minVertexLeft[i] = 1;

	cout << 2 * N - matchingSize << '\n';
	for (i = 1; i <= N; ++i) {
		if (minVertexLeft[i] == 0 && minVertexRight[i] == 0)
			cout << "3\n";
		else if (minVertexRight[i] == 0)
			cout << "2\n";
		else if (minVertexLeft[i] == 0)
			cout << "1\n";
		else
			cout << "0\n";
	}

	return 0;
}