#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) {
    if(vis[cur]) return false;
    vis[cur] = true;

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

void get_match(const vector<vector<int>> &graph, vector<int> &lmatch, vector<int> &rmatch) {
    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)) {
                cont = true;
            }
        }
    } while(cont);
}

void dfs_mis(const int &cur, const bool &side, const vector<vector<int>> &graph, const vector<int> &lmatch,
             const vector<int> &rmatch, vector<bool> &lvis, vector<bool> &rvis) {
    if(side == 0) {
        lvis[cur] = true;
        for(const auto nxt : graph[cur]) {
            if(nxt == lmatch[cur]) continue;
            if(rvis[nxt]) continue;
            dfs_mis(nxt, 1, graph, lmatch, rmatch, lvis, rvis);
        }
    }
    else {
        rvis[cur] = true;
        const int nxt = rmatch[cur];
        if(nxt == -1) return;
        if(lvis[nxt]) return;
        dfs_mis(nxt, 0, graph, lmatch, 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);

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

    for(int i = 0; i < nodes; i++) {
        if(lvis[i]) {
            total_cnt++;
            if(!rvis[i]) {
                total_cnt++;
                fin_state[i] = 3;
            }
            else fin_state[i] = 1;
        }
        else if(!rvis[i]) {
            total_cnt++;
            fin_state[i] = 2;
        }
        else fin_state[i] = 0;
    }
}

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 << total_cnt << '\n';
    for(int i = 0; i < n; i++) {
        out << fin_state[i] << '\n';
    }

    return 0;
}