#include <cstdio>
#include <vector>
#include <bitset>
using namespace std;

const int NMAX = 8193;

vector <short> BG[NMAX];
bitset <NMAX> check, support_left, support_right;
short left[NMAX], right[NMAX], N;

bool pair_up (const short &node) {

    if (check[node])
        return 0;
    vector <short> :: iterator i;
    check[node] = 1;
    for (i = BG[node].begin (); i != BG[node].end (); ++i)
        if (!right[*i]) {
            left[node] = *i;
            right[*i] = node;
            return 1;
        }
    for (i = BG[node].begin (); i != BG[node].end (); ++i)
        if (pair_up (right[*i])) {
            left[node] = *i;
            right[*i] = node;
            return 1;
        }
    return 0;

}

inline void max_matching () {

    short i;
    bool t;
    do {
        t = 0;
        check.reset ();
        for (i = 1; i <= N; ++i)
            if (!left[i])
                t |= pair_up (i);
    }
    while (t);

}

void support (const short &node) {

    vector <short> :: iterator i;
    for (i = BG[node].begin (); i != BG[node].end (); ++i)
        if (!support_right[*i]) {
            support_right[*i] = 1;
            support_left[right[*i]] = 0;
            support (right[*i]);
        }

}

inline void min_support () {

    short i;
    for (i = 1; i <= N; ++i)
        if (left[i])
            support_left[i] = 1;
    for (i = 1; i <= N; ++i)
        if (!support_left[i])
            support (i);


}

int main () {

    freopen ("felinare.in", "r", stdin);
    freopen ("felinare.out", "w", stdout);
    short M, i, a, b, ans = 0;
    scanf ("%hd%hd", &N, &M);
    for (i = 1; i <= M; ++i) {
        scanf ("%hd%hd", &a, &b);
        BG[a].push_back (b);
    }
    max_matching ();
    min_support ();
    for (i = 1; i <= N; ++i)
        ans += 2 - support_left[i] - support_right[i];
    printf ("%hd", ans);
    for (i = 1; i <= N; ++i) {
        ans = 0;
        ans += 2 * (!support_right[i]) + (!support_left[i]);
        printf ("\n%hd", ans);
    }

}