#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;

const int N = 9000;

int sr[N], sl[N], n, m, st[N], dr[N], c;
vector<int> v[N];
bool u[N];

bool pairup(int nod) {
	if(u[nod])
		return false;
	u[nod] = true;
	
	for(vector<int>::iterator it = v[nod].begin(); it != v[nod].end(); ++it)
		if(!st[*it] || pairup(st[*it])) {
			
			dr[nod] = *it;
			st[*it] = nod;
			
			sr[nod] = 1;
			return true;
		}
	
	return false;
}

void cuplaj() {
	int o = 1, i;
	
	while(o) {
		o = 0;
		
		for(i = 1; i<=n; ++i)
			u[i] = false;
		
		for(i = 1; i<=n; ++i) if(!dr[i] && pairup(i)) {
			++c;
			o = 1;
		}
	}
}

void suport(int nod) {
	for(vector<int>::iterator it = v[nod].begin(); it != v[nod].end(); ++it)
		if(!sl[*it]) {
			sl[*it] = 1;
			sr[st[*it]] = 0;
			
			suport(st[*it]);
		}
}

int main() {
	int i, a, b;
	
	freopen("felinare.in", "r", stdin);
	freopen("felinare.out", "w", stdout);
	
	cin >> n >> m;
	
	for(i = 1; i<=m; ++i) {
		cin >> a >> b;
		
		v[a].push_back(b);
	}
	
	cuplaj();
	
	for(i = 1; i<=n; ++i)
		if(!sr[i])
			suport(i);
	
	cout << 2 * n - c << "\n";
	
	for(i = 1; i<=n; ++i) {
		
		if(sr[i])
			cout << (sl[i] ? "0" : "2") << "\n";
		else
			cout << (sl[i] ? "1" : "3") << "\n";
	}
	
	return 0;
}