#include <cstdio>
#include <vector>
#include <cassert>
using namespace std;

const int NMAX = 16505;
int N, M;
vector<int> G[NMAX];
int L[NMAX], R[NMAX];

void read() {
	scanf("%d%d", &N, &M);
	int x, y;
	for (int edge = 0; edge < M; edge++) {
		scanf("%d%d", &x, &y);
		G[x].push_back(y + N);
	}
}

bool dfs(int node, vector<bool>& visited) {
	if (visited[node]) {
		return false;
	}

	visited[node] = true;
	for (auto& nodeRight : G[node]) {
		if (!R[nodeRight] || dfs(R[nodeRight], visited)) {
			L[node] = nodeRight;
			R[nodeRight] = node;
			return true;
		}
	}

	return false;
}

void alternate(int node, vector<bool>& visited) {
	if (visited[node]) {
		return;
	}

	visited[node] = true;
	for (auto& nodeRight : G[node]) {
		visited[nodeRight] = true;
		// otherwise, not a maximal match
		assert(R[nodeRight]);
		alternate(R[nodeRight], visited);
	}
}

void solve() {
	vector<bool> visited;
	bool foundImprovement = true;
	int totalMatches = 0;
	while (foundImprovement) {
		visited.assign(2 * N + 1, false);
		foundImprovement = false;

		for (int node = 1; node <= N; node++) {
			if (!L[node] && dfs(node, visited)) {
				totalMatches++;
				foundImprovement = true;
			}
		}
	}

	visited.assign(2 * N + 1, false);
	for (int node = 1; node <= N; node++) {
		if (!L[node]) {
			alternate(node, visited);
		}
	}

	vector<bool> minimumVertexCover(2 * N + 1, false);
	// L \ visited union (R intersection visited)
	for (int node = 1; node <= N; node++) {
		if (!visited[node]) {
			minimumVertexCover[node] = true;
		}
	}
	// R intersection visited
	for (int node = N + 1; node <= 2 * N; node++) {
		if (visited[node]) {
			minimumVertexCover[node] = true;
		}
	}

	printf("%d\n", 2 * N - totalMatches);
	// we want maximum independent set here
	for (int node = 1; node <= N; node++) {
		int state = 0;
		if (!minimumVertexCover[node]) {
			state |= 1;
		}
		if (!minimumVertexCover[node + N]) {
			state |= 2;
		}
		printf("%d\n", state);
	}
}

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

	read();
	solve();
	return 0;
}