#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), 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;
				return 1;
			}
		return 0;
	};
	for (int i = 1; i <= n; ++i)
		seen.assign(n + 1, 0), ans += dfs(i);
	ans = 2 * n - ans;
	cout << ans << '\n';
	for (int i = 1; i <= n; ++i)
		sol[p[i]] -= 1;
	for (int i = 1; i <= n; ++i)
		cout << sol[i] << '\n';
}