#include <bits/stdc++.h>

using namespace std;
class Matcher {
    int n, m;
    vector <int> l, r;
    vector <bool> upd;
    vector <vector <int>> g;
    vector <bool> isOn1, isOn2;
    inline bool pairup(int u) {
        if(upd[u]) return false;
        upd[u] = true;
        for(int v : g[u]) if(!l[v])
            return (l[r[u] = v] = u);
        for(int v : g[u]) if(pairup(l[v]))
            return (l[r[u] = v] = u);
        return false;
    }
    void fill01(int u) {
        for(int v : g[u]) if(isOn2[v]) {
            isOn2[v] = false;
            isOn1[l[v]] = true;
            fill01(l[v]);
        }
    }
public:
    Matcher(int n, int m) : n(n), m(m), l(m + 1, 0), r(n + 1, 0), upd(n + 1), g(n + 1), isOn1(n + 1, true), isOn2(m + 1, true) {}
    void add_edge(int u, int v) { g[u].push_back(v); }
    int match() {
        for(bool ok = true; ok; ) {
            ok = false;
            fill(upd.begin(), upd.end(), false);
            for(int i = 1; i <= n; i++) if(!r[i])
                ok |= pairup(i);
        }
        int ans = 0;
        for(int i = 1; i <= n; i++)
            if(r[i]) {
                ans++;
                isOn1[i] = false;
            }
        return ans;
    }
    void flood() {
        for(int i = 1; i <= n; i++) if(!r[i])
            fill01(i);
    }
    void get_light_map(vector <int>& sol) {
        sol.resize(n);
        for(int i = 1; i <= n; i++) {
            int val = isOn1[i] | (isOn2[i] << 1);
            sol[i - 1] = val;
        }
    }
};

int main()
{
    ifstream cin("felinare.in");
    ofstream cout("felinare.out");
    int n, m, u, v;
    cin >> n >> m;
    Matcher M(n, n);
    for(int i = 1; i <= m; i++)
        cin >> u >> v,
        M.add_edge(u, v);
    cout << 2 * n - M.match() << "\n";
    M.flood();
    vector <int> sol;
    M.get_light_map(sol);
    for(int x : sol)
        cout << x << "\n";
    return 0;
}