#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <functional>

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

int gs, edg;
std::vector<std::vector<int>> adj_list;
std::vector<std::pair<int,int>> edges;
std::vector<int> match_l;
std::vector<int> match_r;
int in_mvc[20005];
int in_mis[20005];

void read_graph() {
	fin >> gs >> edg;
	adj_list.resize(gs);
	match_l.assign(gs, -1);
	match_r.assign(gs, -1);

	for (int i = 0, a, b; i < edg; i++) {
		fin >> a >> b; --a, --b;
		edges.emplace_back(a,b);
		adj_list[a].emplace_back(b);
	}
}

void max_independent_set() {
	const std::function<void()> max_bipartite_matching = [&]() {
		std::vector<bool> vis(gs, 0);

		const std::function<bool(int)> try_kuhn = [&](int k) {
			if (vis[k]) {
				return false;
			}

			vis[k] = 1;
			for (const auto& i : adj_list[k]) {
				if (match_r[i]==-1||try_kuhn(match_r[i])) {
					match_l[k] = i;
					match_r[i] = k;
					return true;
				}
			}

			return false;
		};

		while (1) {
			std::fill(vis.begin(), vis.end(), 0);
			bool done = 1;
			for (int i = 0; i < gs; i++) {
				if (match_l[i]==-1) {
					done &= !try_kuhn(i);
				}
			}
			if (done) {
				break;
			}
		}
	};

	const std::function<void()> construct_solution = [&]() {
		adj_list.assign(2*gs, std::vector<int>());
		std::vector<bool> vis(gs, 0);
		for (const auto& [a, b] : edges) {
			if (match_l[a]==b) {
				adj_list[a].emplace_back(b+gs);
			}
			else {
				adj_list[b+gs].emplace_back(a);
			}
		}

		const std::function<void(int)> dfs = [&](int k) {
			vis[k] = 1;
			for (const auto& i : adj_list[k]) {
				if (!vis[i]) {
					dfs(i);
				}
			}
		};

		for (int i = 0; i < gs; i++) {
			if (!vis[i]&&match_l[i]==-1) {
				dfs(i);
			}
		}

		int ret = 2*gs;
		for (int i = 0; i < gs; i++) {
			if (match_l[i]!=-1) {
				ret -= 1;
				if (!vis[i]) {
					in_mvc[i] = 1;
				}
			}
			else if (match_r[i]!=-1) {
				if (vis[i+gs]) {
					in_mvc[i+gs] = 1;
				}
			}
		}

		for (int i = 0; i < 2*gs; i++) {
			in_mis[i] = !in_mvc[i];
		}
		
		fout << ret << "\n";
		for (int i = 0; i < gs; i++) {
			fout << (in_mis[i] | (in_mis[i+gs]<<1)) << "\n";
		}
	};

	max_bipartite_matching();
	construct_solution();
}

int main() {
	read_graph();
	max_independent_set();
}