#include <fstream>
#include <vector>
#include <cstring>
using namespace std;

const int kMaxN = 8200;

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

int N, M, l[kMaxN], r[kMaxN], sol;
vector<int> G[kMaxN];
bool use[kMaxN], use_l[kMaxN], use_r[kMaxN];

void Read() {
	fin >> N >> M;
	while (M--) {
		int x, y;
		fin >> x >> y;
		G[x].push_back(y);
	}
}

inline void Connect(int a, int b) {
	l[a] = b;
	r[b] = a;
	use_l[a] = true;
}

bool Link(int node) {
	if (use[node])
		return false;
	use[node] = true;
	for (int i : G[node])
		if (!r[i]) {
			Connect(node, i);
			return true;
		}
	for (int i : G[node])
		if (Link(r[i])) {
			Connect(node, i);
			return true;
		}
	return false;
}

void Match() {
	bool ok = true;
	while (ok) {
		ok = false;
		memset(use, 0, sizeof use);
		for (int i = 1; i <= N; ++i)
			if (!l[i])
				ok |= Link(i);
	}
	for (int i = 1; i <= N; ++i)
		if (l[i])
			++sol;
}

void SupportLink(int node) {
	for (int i : G[node])
		if (!use_r[i]) {
			use_l[r[i]] = false;
			use_r[i] = true;
			SupportLink(r[i]);
		}
}

void Support() {
	for (int i = 1; i <= N; ++i)
		if (!use_l[i])
			SupportLink(i);
}

void Print() {
	fout << 2 * N - sol << "\n";
	for (int i = 1; i <= N; ++i)
		fout << (((1 ^ use_r[i]) << 1) + (1 ^ use_l[i])) << "\n";
}

int main() {
	Read();
	Match();
	Support();
	Print();
	return 0;
}