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

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

const int N = 8200;

int n, m, A[N], B[N], sol, wh[N];
vector <short> g[N];
vector <bool> viz(N, 0);

bool match(int x) {
    if (viz[x])
        return 0;
    viz[x] = 1;
    for (vector <short> :: iterator it = g[x].begin(); it != g[x].end(); ++it)
        if (!B[*it]) {
            B[*it] = x;
            A[x] = *it;
            return 1;
        }
    for (vector <short> :: iterator it = g[x].begin(); it != g[x].end(); ++it)
        if (match(B[*it])) {
            A[x] = *it;
            B[*it] = x;
            return 1;
        }
    return 0;
}

int main() {
    fin >> n >> m;
    for (int x, y, i = 0; i < m; ++i) {
        fin >> x >> y;
        g[x].push_back (y);
    }
    bool done = 1;
    while (done) {
        done = 0;
        viz.assign(n + 1, 0);
        for (int i = 1; i <= n; ++i)
            if (!A[i])
                done |= match(i);
    }
    for (int i = 1; i <= n; ++i)
        sol += A[i] > 0;
    sol = n * 2 - sol;
    fout << sol << "\n";
    for (int i = 1; i <= n; ++i) {
        if (!A[i])
            wh[i] += 1;
        if (!B[i])
            wh[i] += 2;
    }
    for (int i = 1; i <= n; ++i) {
        if (wh[i] == 1 || wh[i] == 2)
            sol--;
        if (wh[i] == 3)
            sol -= 2;
        fout << wh[i] << "\n";
    }
}