#include <bits/stdc++.h>

using namespace std;

const int MAXN = 8200;
vector< int > gr[MAXN];
int viz[MAXN];
int l[MAXN];
int r[MAXN];

int cl[MAXN];
int cr[MAXN];

int step = 0;
int matched = 0;
bool cuplaj(int node) {
    if(viz[node] == step) return false;

    viz[node] = step;

    for(auto &x : gr[node]) {
        if(!r[x]) {
            r[x] = node;
            l[node] = x;
            ++matched;
            return true;
        }
    }

    for(auto &x : gr[node]) {
        if(cuplaj(r[x])) {
            r[x] = node;
            l[node] = x;
            return true;
        }
    }

    return false;
}

void dfs(int node) {
    for(auto &x : gr[node]) {
        if(!cr[x]) {
            cr[x] = true;
            cl[r[x]] = false;
            dfs(r[x]);
        }
    }
}
int main () {
    #ifdef HOME
        freopen("input", "r", stdin);
        #define f cin
        #define g cout
    #else
        ifstream f("felinare.in");
        ofstream g("felinare.out");
    #endif // HOME

    int n, m;
    f >> n >> m;

    for(int i = 1; i <= m; ++i) {
        int a, b;
        f >> a >> b;

        gr[a].emplace_back(b);
    }

    bool ok = true;
    while(ok) {
        ok = false;
        ++step;
        for(int i = 1; i <= n; ++i) {
            if(!l[i]) ok |= cuplaj(i);
        }
    }

    for(int i = 1; i <= n; ++i) {
        if(l[i]) cl[i] = 1;
    }

    for(int i = 1; i <= n; ++i) {
        if(!l[i]) dfs(i);
    }

    g << 2*n - matched << '\n';

    for(int i = 1; i <= n; ++i) {
        g << 3 - 2*cr[i] - cl[i] << '\n';
    }
    return 0;
}