#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 1e4 + 5;

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

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

inline void DFS(int nod) {
    for (auto vecin : g[nod]) {
        if (!l[vecin]) {
            l[vecin] = 1;
            l[st[vecin]] = 0;
            DFS(st[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) {
        for (int i = 1; i <= n; ++i)
            f[i] = 0;
        ok = 0;
        for (int i = 1; i <= n; ++i) {
            if (!f[i] && !dr[i] && cupleaza(i))
                ok = 1;
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (dr[i])
            r[i] = 1;
    }
    for (int i = 1; i <= n; ++i) {
        if (!dr[i])
            DFS(i);
    }
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        if (!l[i])
            ++cnt;
        if (!r[i])
            ++cnt;
    }
    out << cnt << '\n';
    for (int i = 1; i <= n; ++i) {
        if (!l[i] && !r[i])
            out << 3;
        else if (!r[i])
            out << 1;
        else if (!l[i])
            out << 2;
        else
            out << 0;
        out << '\n';
    }
    return 0;
}