#include <bits/stdc++.h>

using namespace std;

const int N = 8193;

int n, m, l[N], r[N], sl[N], sr[N];
vector<int>g[N];
bool vis[N];

bool dfs(int nod_st) {
	if(vis[nod_st]) {
		return false;
	}
	vis[nod_st] = true;
	for(auto nod_dr : g[nod_st]) {
		if(!l[nod_dr] || dfs(l[nod_dr])) {
			l[nod_dr] = nod_st;
			r[nod_st] = nod_dr;
			return true;
		}
	}
	return false;
}

void cover(int nod_st) {
	for(auto nod_dr : g[nod_st]) {
		if(!sr[nod_dr]) {
			sr[nod_dr] = true;
			sl[l[nod_dr]] = false;
			cover(l[nod_dr]);
		}
	}
}
int main() {

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

	cin >> n >> m;
	for(int i = 1; i <= m; ++i) {
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
	}

	for(bool augp = 1; augp;) {
		augp = 0;
		memset(vis, 0, sizeof vis);
		for(int i = 1; i <= n; ++i) {
			if(!r[i]) {
				augp |= dfs(i);
			}
		}
	}

	for(int i = 1; i <= n; ++i) {
		if(!r[i]) {
			sl[i] = false;
		} else sl[i] = true;
	}

	for(int i = 1; i <= n; ++i)
		if(!sl[i])
			cover(i);

    int mis = 2 * n;
    for(int i = 1; i <= n; ++i)
    {
        if(sl[i]) mis--;
        if(sr[i]) mis--;
    }
    cout << mis << '\n';
    for(int i = 1; i <= n; ++i)
    {
        if(sl[i] && sr[i])
            cout << 0 << '\n';
        else if(sl[i]) cout << 2 << '\n';
        else if(sr[i]) cout << 1 << '\n';
        else cout << 3 << '\n';
    }
}