#include <bits/stdc++.h>

using namespace std;

ifstream fin("felinare.in");
ofstream fout("felinare.out");
int n, m, i, j, per[8202], inv[8202], rasp;
//vector<int> gri[102];
vector<int> gro[8202];
bool viz[8202];
bool apr[8202];

static inline bool Cuplu(int nod) {
    if(viz[nod]) return false;
    viz[nod] = true;
    for(int urm : gro[nod]) {
        if(!per[urm] || Cuplu(per[urm])) {
            apr[nod] = true;
            per[nod] = urm;
            inv[urm] = nod;
            return true;
        }
    }
    return false;
}

static inline void DFS(int nod) {
    for(int urm : gro[nod]) {
        if(!viz[urm]) {
            apr[per[urm]] = false;
            viz[urm] = true;
            DFS(per[urm]);
        }
    }
}

int main() {
    //ios_base::sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);

    fin >> n >> m;
    for(i = 1; i <= m; i++) {
        int x, y;
        fin >> x >> y;
        //gri[y].push_back(x);
        gro[x].push_back(y);
    }

    rasp = 0;
    for(i = 1; i <= n; i++) {
        if(!per[i] && Cuplu(i)) {
            memset(viz, false, sizeof(viz));
            rasp++;
        }
    }

    memset(viz, false, sizeof(viz));
    fout << 2 * n - rasp << "\n";
    for(i = 1; i <= n; i++) {
        if(!apr[i]) DFS(i);
    }

    for(i = 1; i <= n; i++) {
        fout << 3 - (apr[i] + 2 * viz[i]) << "\n";
    }

    return 0;
}