#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;
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;
    fout << n * 2 - sol << "\n";
    for (int i = 1; i <= n; ++i) {
        int wh = 0;
        if (A[i] >= 0) {
            wh = 1;
            if (A[i])
                B[A[i]] = -1;
            if (B[i] >= 0) {
                wh = 3;
                if (B[i])
                    A[B[i]] = -1;
            }
        }
        else
            if (B[i] >= 0) {
                wh = 2;
                if (B[i])
                    A[B[i]] = -1;
            }
        fout << wh << "\n";
    }

}