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

int n, m;
int covered[20001];
vector<int> a[8201];

void read() {
    int i, x, y;
    ifstream f("felinare.in");
    f >> n >> m;
    for (i = 1; i <= m; i++) {
        f >> x >> y;
        a[x].push_back(y);
    }
    f.close();
}

int l[8201], r[8201], viz[8201];
int rez;

bool pair_up(int x) {
    int i;
    viz[x] = 1;
    for (i = 0; i < a[x].size(); i++)
        if (l[a[x][i]] == 0) {
            r[x] = a[x][i];
            l[a[x][i]] = x;
            return 1;
        }
    for (i = 0; i < a[x].size(); i++)
        if (!viz[l[a[x][i]]] && pair_up(l[a[x][i]])) {
            r[x] = a[x][i];
            l[a[x][i]] = x;
            return 1;
        }
    return 0;
}

void cover_up(int x) {
    int i;
    viz[x] = 1;
    for (i = 0; i < a[x].size(); i++)
        if (!viz[a[x][i]] && covered[a[x][i] + n] == 0) {
            covered[l[a[x][i]]] = 0;
            covered[a[x][i] + n] = 1;
            cover_up(l[a[x][i]]);
        }
}

void solve() {
    int i;
    bool ok;
    do {
        ok = 0;
        for (i = 1; i <= n; i++)
            viz[i] = 0;
        for (i = 1; i <= n; i++)
            if (r[i] == 0 && pair_up(i))
                ok = 1;
    } while(ok == 1);

    for (i = 1; i <= n; i++)
        if (r[i]) {
            rez++;
            covered[i] = 1;
        }
    rez = 2 * n - rez;
    for (i = 1; i <= n; i++)
        viz[i] = 0;
    for (i = 1; i <= n; i++)
        if (!covered[i])
            cover_up(i);
}

void output() {
    int i;
    ofstream g("felinare.out");
    g << rez << '\n';
    for (i = 1; i <= n; i++)
        g << !(covered[i]) + !(covered[i + n]) * 2 << '\n';
    g.close();
}

int main() {
    read();
    solve();
    output();
    return 0;
}