#include <bits/stdc++.h>
using namespace std;

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

int n, m, in[10000], out[10000];
vector<int> g[10000];
bool v[10000], cover[20000];

bool dfs(int x) {
    v[x] = true;
    for(auto next :g[x])
        if(!in[next] || (!v[in[next]] && dfs(in[next]))) {
            in[next] = x;
            out[x] = next;
            return true;
        }
    return false;
}

void vertexCover(int x) {
    v[x] = true;
    for(auto next: g[x])
        if(!cover[n+next]) {
            cover[n+next] = true;
            cover[in[next]] = false;
            vertexCover(in[next]);
        }
}

int main() {
    fin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u, v;
        fin >> u >> v;
        g[u].push_back(v);
    }

    int nr = 0;
    bool ok = true;
    while(ok) {
        ok = false;
        for(int i = 1; i <= n; i++) v[i] = false;
        for(int i = 1; i <= n; i++)
            if(!v[i] && !out[i] && dfs(i)) {
                nr++;
                ok = true;
            }
    }
    for(int i = 1; i <= n; i++) {
            v[i] = false;
        if(out[i]) cover[i] = true;
    }
    for(int i = 1; i <= n; i++)
        if(!v[i] && !out[i])
            vertexCover(i);


    fout << 2*n-nr << '\n';
    for(int i = 1; i <= n; i++)
        fout << (int)(!cover[i])+2*(int)(!cover[n+i]) << '\n';
}