#include <algorithm>
#include <cstdlib>
#include <fstream>
#include <vector>
using namespace std;
#define FORIT(it, v) for(typeof((v).begin())it=(v).begin();it!=(v).end();++it)

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

const int MAX_N = 8300;

int N, M;
vector<int> graph[MAX_N];
bool visited[MAX_N], marked[2 * MAX_N];
int match[MAX_N], matchedWith[MAX_N];
int intependentSetSize;
int solution[MAX_N];

void read(), solve(), print();
int find_matching();
bool match_node(int node);
void find_independent_set();
void mark_node(int node);

int main() {
	read();
	solve();
	print();
	return 0;
}

void read() {
	fin >> N >> M;
	for (int i = 1; i <= M; ++i) {
		int node1, node2;
		fin >> node1 >> node2;
		graph[node1].push_back(node2);
	}
}

void solve() {
	int matchingSize = find_matching();
	intependentSetSize = 2 * N - matchingSize;
	find_independent_set();
	for (int i = 1; i <= N; ++i) {
		if (marked[i] && marked[N+i]) {
			solution[i] = 0;
		} else if (marked[N+i]) {
			solution[i] = 1;
		} else if (marked[i]) {
			solution[i] = 2;
		} else {
			solution[i] = 3;
		}
	}
}

void print() {
	fout << intependentSetSize << '\n';
	for (int i = 1; i <= N; ++i) {
		fout << solution[i] << '\n';
	}
}

int find_matching() {
	int result = 0;
	bool go;
	do {
		go = false;
		fill(visited, visited + N + 1, 0);
		for (int i = 1; i <= N; ++i) {
			if (!match[i]) {
				if (match_node(i)) {
					++result;
					go = true;
				}
			}
		}
	} while (go);
	return result;
}

bool match_node(int node) {
	if (visited[node] == true) return false;
	visited[node] = true;
	FORIT (it, graph[node]) {
		if (!matchedWith[*it] || match_node(matchedWith[*it])) {
			match[node] = *it;
			matchedWith[*it] = node;
			return true;
		}
	}
	return false;
}

void find_independent_set() {
	for (int i = 1; i <= N; ++i) {
		if (match[i] != 0) {
			marked[i] = true;
		}
	}
	for (int i = 1; i <= N; ++i) {
		if (match[i] == 0) {
			mark_node(i);
		}
	}
}

void mark_node(int node) {
	FORIT (it, graph[node]) {
		if (!marked[N+*it]) {
			marked[N+*it] = true;
			marked[matchedWith[*it]] = false;
			mark_node(matchedWith[*it]);
		}
	}
}