#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 1e4 + 5;

int n, m;
int l[NMAX], r[NMAX];
bool f[NMAX], st[NMAX], dr[NMAX];
vector <int> g[NMAX];

inline bool cupleaza(int nod) {
    f[nod] = 1;
    for (auto vecin : g[nod]) {
        if (!l[vecin]) {
            r[nod] = vecin;
            l[vecin] = nod;
            return 1;
        }
        if (!f[l[vecin]] && cupleaza(l[vecin])) {
            r[nod] = vecin;
            l[vecin] = nod;
            return 1;
        }
    }
    return 0;
}

inline void DFS(int nod) {
    for (auto vecin : g[nod]) {
        if (!st[vecin]) {
            st[vecin] = 1;
            dr[l[vecin]] = 0;
            DFS(l[vecin]);
        }
    }
}

int main() {
    int x, y;
    in >> n >> m;
    for (int i = 1; i <= m; ++i) {
        in >> x >> y;
        g[x].push_back(y);
    }
    bool ok = 1;
    while (ok) {
        ok = 0;
        memset(f, 0, sizeof(f));
        for (int i = 1; i <= n; ++i) {
            if (!f[i] && !r[i] && cupleaza(i))
                ok = 1;
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (r[i])
            dr[i] = 1;
    }
    for (int i = 1; i <= n; ++i) {
        if (!r[i])
            DFS(i);
    }
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        if (!st[i])
            ++cnt;
        if (!dr[i])
            ++cnt;
    }
    out << cnt << '\n';
    for (int i = 1; i <= n; ++i) {
        if (!st[i] && !dr[i])
            out << 3;
        else if (!dr[i])
            out << 1;
        else if (!st[i])
            out << 2;
        else
            out << 0;
        out << '\n';
    }
    return 0;
}