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

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

vector <int> adia_st[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;
			if (activ_st[cuplat_dr[i]])
					dezactiv(cuplat_dr[i]);
		}
	}
}

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

	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--;

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

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

	out << ans << '\n';

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

	return 0;
}