#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], ca[N], cb[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;
            ca[x] = 1;
            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;
            ca[x] = 1;
            return 1;
        }
    return 0;
}
 
void dfs(int x) {
    for (vector <short> :: iterator it = g[x].begin(); it != g[x].end(); ++it)
        if (!cb[*it]) {
            cb[*it] = 1;
            ca[B[*it]] = 0;
            dfs (B[*it]);
        }
}
 
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 (!ca[i])
            dfs(i);
    for (int wh = 0, i = 1; i <= n; ++i) {
        wh = 0;
        if (!ca[i])
            wh++;
        if (!cb[i])
            wh += 2;
        fout << wh << "\n";
    }
}