# include <algorithm>
# include <cstdio>
# include <cstring>
# include <vector>
using namespace std;

const char *FIN = "felinare.in", *FOU = "felinare.out";
const int MAX = 8195;

vector <int> G[MAX];
int N, M, E, st[MAX], dr[MAX], vst[MAX], vdr[MAX], viz[MAX];

bool dfs (int S) {
    if (viz[S]) return 0;
    else viz[S] = 1;
    for (vector <int> :: iterator it = G[S].begin (); it != G[S].end (); ++it)
        if (st[*it] == 0 || dfs (st[*it])) {
            st[*it] = S, dr[S] = *it, vst[S] = 1;
            return 1;
        }
    return 0;
}

void solve (int S) {
    for (vector <int> :: iterator it = G[S].begin (); it != G[S].end (); ++it)
        if (vdr[*it] == 0) {
            vdr[*it] = 1, vst[st[*it]] = 0;
            solve (st[*it]);
        }
}

int main (void) {
    freopen (FIN, "r", stdin);
    freopen (FOU, "w", stdout);

    scanf ("%d %d", &N, &M);
    for (int i = 1, x, y; i <= M; ++i) {
        scanf ("%d %d", &x, &y);
        G[x].push_back (y);
    }
    for (int sol = 1; sol;) {
        sol = 0, memset (viz, 0, sizeof (viz));
        for (int i = 1; i <= N; ++i)
            if (dr[i] == 0) sol |= dfs (i);
    }
    int sol = 0;
    for (int i = 1; i <= N; ++i)
        sol += dr[i] > 0;
    for (int i = 1; i <= N; ++i) {
        if (vst[i]) continue;
        solve (i);
    }
    printf ("%d\n", 2 * N - sol);
    for (int i = 1; i <= N; ++i)
        printf ("%d\n", 1 - vst[i] + 2 * (1 - vdr[i]));
}