#include <bits/stdc++.h>

using namespace std;

int main() {
	ifstream cin("felinare.in");
	ofstream cout("felinare.out");
	int n, m, x, y, ans = 0;
	cin >> n >> m;
	vector<int> seen(n + 1), p(n + 1), s(n + 1), sol(n + 1);
	vector<vector<int>> G(n + 1);
	while (m--) {
		cin >> x >> y;
		G[x].emplace_back(y);
	}
	function<int(int)> dfs = [&](int node) {
		seen[node] = 1;
		for (auto x : G[node])
			if (!p[x] || (!seen[p[x]] && dfs(p[x]))) {
				p[x] = node;
				sol[node] = 1;
				return 1;
			}
		return 0;
	};
	for (int i = 1; i <= n; ++i)
		ans += dfs(i), seen.assign(n + 1, 0);
	ans = 2 * n - ans;
	cout << ans << '\n';
	function<void(int)> dfs2 = [&](int node) {
		seen[node] = 1;
		for (auto x : G[node])
			if (!(sol[x] & 2)) {
				sol[x] |= 2;
				sol[p[x]] ^= 1;
				if (!seen[p[x]])
					dfs2(p[x]);
			}
	};
	for (int i = 1; i <= n; ++i)
		if (!(sol[i] & 1))
			dfs2(i);
	for (int i = 1; i <= n; ++i)
		cout << (sol[i] ^ 3) << '\n';
}