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

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

vector <int> adia_st[100010], adia_dr[100010];
int viz[100010];
int cuplat_st[100010], cuplat_dr[100010];
int activ_st[100010], activ_dr[100010];

bool cuplaj(int nod)
{
	viz[nod] = 1;
	for (auto i : adia_st[nod]) {
		if (!cuplat_dr[i]) {
			cuplat_dr[i] = nod;
			cuplat_st[nod] = i;
			return true;
		}
	}
	for (auto i : adia_st[nod]) {
		if (!viz[cuplat_dr[i]] && cuplaj(cuplat_dr[i])) {
			cuplat_dr[i] = nod;
			cuplat_st[nod] = i;
			return true;
		}
	}
	return false;
}

void dezactiv(int nod_st)
{
	activ_st[nod_st] = 0;
	for (auto i : adia_st[nod_st]) {
		if (!activ_dr[i]) {
			activ_dr[i] = 1;
			for (auto j : adia_dr[i])
				if (activ_st[j])
					dezactiv(j);
		}
	}
}

int main()
{
	int n, m, a, b;
	in >> n >> m;
	
	while (m--) {
		in >> a >> b;
		adia_st[a].push_back(b);
		adia_dr[b].push_back(a);
	}

	bool made = 1;
	while (made) {
		made = 0;
		memset(viz, 0, sizeof viz);
		for (int i = 1; i <= n; i++)
			if (!viz[i] && !cuplat_st[i] && cuplaj(i))
				made = 1;
	}

	int ans = 2 * n;
	for (int i = 1; i <= n; i++)
		if (cuplat_st[i])
			ans--, activ_st[i] = 1;

	for (int i = 1; i <= n; i++)
		if (!activ_st[i])
			dezactiv(i);

	out << ans << '\n';

	for (int i = 1; i <= n; i++)
		for (auto j : adia_st[i])
			assert(activ_st[i] || activ_dr[j]);

	int s = 2 * n;

	for (int i = 1; i <= n; i++)
		s -= activ_st[i], s -= activ_dr[i];

	assert(s == ans);

	for (int i = 1; i <= n; i++)
		out << 1 * (activ_st[i] ^ 1) + 2 * (activ_dr[i] ^ 1) << '\n';

	return 0;
}