#include <bits/stdc++.h>
 
using namespace std;

#define all(x) (x).begin(), (x).end()

const int MAXN = 8192;

bool viz[MAXN];
int r[MAXN];
int l[MAXN];
bool usel[MAXN];
bool user[MAXN];

vector< int > gr[MAXN];
int matched = 0;
bool cuplaj(int node) {
	if(viz[node]) return false;
	viz[node] = true;

	for(auto &x : gr[node]) {
		if(!l[x] || cuplaj(l[x])) {
			matched += (!l[x]);
			l[x] = node;
			r[node] = x;
			return true;
		}
	}

	return false;
}

void dfs(int node) {
	for(auto &x : gr[node]) {
		if(!user[x]) {
			user[x] = true;
			usel[l[x]] = false;
			dfs(l[x]);
		}
	}

	return;
}

int main() {
	#ifdef BLAT
		freopen("input", "r", stdin);
	#else
		freopen("felinare.in", "r", stdin);
		freopen("felinare.out", "w", stdout);
	#endif
 
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	srand(time(nullptr));

	int n, m;
	cin >> n >> m;

	for(int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		gr[a].emplace_back(b);
	}

	bool ok = true;
	while(ok) {
		ok = false;
		memset(viz, 0, sizeof viz);
		for(int i = 1; i <= n; ++i) {
			if(!r[i]) ok |= cuplaj(i);
		}
	}

	for(int i = 1; i <= n; ++i) {
		if(r[i]) usel[i] = true;
	}
	for(int i = 1; i <= n; ++i) {
		if(!r[i]) dfs(i);
	}

	cout << 2*n - matched << '\n';
	for(int i = 1; i <= n; ++i) {
		cout << 3 - usel[i] - 2*user[i] << '\n';	
	}
	return 0;
}