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

ifstream fi("felinare.in");
ofstream fo("felinare.out");

const int N = 8200;

vector<int> g[N];
int l[N], r[N];
bool f[N], s_st[N], s_dr[N];

int n, m;

bool match(int u) {
	if (f[u]) return false;
	f[u] = true;

	for (auto v: g[u]) if (!r[v]) {
		l[u] = v;
		r[v] = u;
		return true; }

	for (auto v: g[u]) if (match(r[v])) {
		l[u] = v;
		r[v] = u;
		return true; }

	return false; }

void support(int u) {
	for (auto v: g[u]) if (!s_dr[v]) {
		s_dr[v] = 1;
		s_st[r[v]] = 0;
		support(r[v]); } }

int main() {
	int a, b, ant(0);
	bool flag;

	fi >> n >> m;
	for (int i = 0; i < m; ++i) {
		fi >> a >> b;
		g[a].push_back(b); }

	do {
		flag = false;
		memset(f, 0x00, sizeof f);
		for (int i = 1; i <= n; ++i)
			if (!l[i] && match(i)) {
				flag = true;
				ant++; } }
	while (flag);

	for (int i = 1; i <= n; ++i)
		s_st[i] = l[i];

	for (int i = 1; i <= n; ++i) if (!s_st[i])
		support(i);

	fo << n * 2 - ant << '\n';
	for (int i = 1; i <= n; ++i)
		fo << int(s_st[i] == 0) + int(s_dr[i] == 0) * 2 << '\n';

	return 0; }