#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

bool pair_up(const int &cur, const vector<vector<int>> &graph, vector<int> &lmatch, vector<int> &rmatch,
             vector<bool> &vis, vector<bool> &lvis) {
    if(vis[cur]) return false;
    vis[cur] = true;

    for(const auto nxt : graph[cur]) {
        if(rmatch[nxt] == -1) {
            lmatch[cur] = nxt;
            rmatch[nxt] = cur;
            lvis[cur] = true;
            return true;
        }
    }
    for(const auto nxt : graph[cur]) {
        if(pair_up(rmatch[nxt], graph, lmatch, rmatch, vis, lvis)) {
            lmatch[cur] = nxt;
            rmatch[nxt] = cur;
            lvis[cur] = true;
            return true;
        }
    }
    return false;
}

void get_match(const vector<vector<int>> &graph, vector<int> &lmatch, vector<int> &rmatch, vector<bool> &lvis,
               int &total_cnt) {
    const int lsz = lmatch.size();
    const int rsz = rmatch.size();
    vector<bool> vis(lsz, false);

    bool cont;
    do {
        cont = false;
        fill(begin(vis), end(vis), false);
        for(int i = 0; i < lsz; i++) {
            if(lmatch[i] == -1 && pair_up(i, graph, lmatch, rmatch, vis, lvis)) {
                cont = true;
                total_cnt++;
            }
        }
    } while(cont);
}

void dfs_mis(const int &cur, const vector<vector<int>> &graph, const vector<int> &rmatch,
             vector<bool> &lvis, vector<bool> &rvis) {
    for(const auto nxt : graph[cur]) {
        if(rvis[nxt]) continue;
        rvis[nxt] = true;
        lvis[rmatch[nxt]] = false;
        dfs_mis(rmatch[nxt], graph, rmatch, lvis, rvis);
    }
}

void get_lamps(const vector<vector<int>> &graph, vector<int> &lmatch, vector<int> &rmatch,
               vector<int> &fin_state, int &total_cnt){
    const int nodes = graph.size();
    vector<bool> lvis(nodes, false);
    vector<bool> rvis(nodes, false);

    get_match(graph, lmatch, rmatch, lvis, total_cnt);

    for(int i = 0; i < nodes; i++) {
        if(lmatch[i] != -1) continue;
        dfs_mis(i, graph, rmatch, lvis, rvis);
    }

    for(int i = 0; i < nodes; i++) {
        fin_state[i] = 3 - lvis[i] - 2 * rvis[i];
    }
}

int main() {
    int n, m;

    in >> n >> m;

    vector<vector<int>> graph(n);

    for(int i = 0, a, b; i < m; i++) {
        in >> a >> b;
        --a; --b;
        graph[a].push_back(b);
    }

    vector<int> lmatch(n, -1);
    vector<int> rmatch(n, -1);
    vector<int> fin_state(n, 0);
    int total_cnt = 0;

    get_lamps(graph, lmatch, rmatch, fin_state, total_cnt);

    out << 2 * n - total_cnt << '\n';
    for(int i = 0; i < n; i++) {
        out << fin_state[i] << '\n';
    }

    return 0;
}