#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, 3);
	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] << '\n';
}