#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

const int N = 8200;

vector <int> graph [2 * N];
int n;
bool used [N];
int a [2 * N], b [2 * N], mvc [2 * N], sol [N];

int cuplaj (int x) {
    vector <int> :: iterator it;

    if (used [x] == 1)
        return 0;
    used [x] = 1;
    for (it = graph [x].begin (); it != graph [x].end (); ++ it)
        if (b [*it] == 0) {
            a [x] = *it;
            b [*it] = x;
            return 1;
        }
    for (it = graph [x].begin (); it != graph [x].end (); ++ it)
        if (b [*it]) {
            if (cuplaj (b [*it]) == 1) {
                a [x] = *it;
                b [*it] = x;
                return 1;
            }
        }
    return 0;
}

void dfs (int x) {
    vector <int> :: iterator it;

    for (it = graph [x].begin (); it != graph [x].end (); ++ it)
       if (mvc [*it] == 0) {
           mvc [*it] = 1;
           mvc [b [*it]] = 0;
           dfs (b [*it]);
       }
}

int main () {
    int i, m, x, y, muchia, lim, ans = 0;
    bool flag;

    freopen ("felinare.in", "r", stdin);
    freopen ("felinare.out", "w", stdout);

    scanf ("%d%d", &n, &m);
    lim = 2 * n;
    for (i = 1; i <= m; i ++) {
        scanf ("%d%d", &x, &y);
        graph [x].push_back (y + n);
    }
    flag = true;
    while (flag) {
        flag = 0;
        memset (used, 0, sizeof (used));
        for (i = 1; i <= n; i ++)
            if (a [i] == 0) {
                if (cuplaj (i)) {
                    flag = 1;
                    ans ++;
                }
            }
    }
    for (i = 1; i <= n; i ++)
        if (a [i])
            mvc [i] = 1;
    for (i = 1; i <= n; i ++)
        if (a [i] == 0)
            dfs (i);
    for (i = 1; i <= n; i ++)
        if (mvc [i] == 0)
            sol [i] = 1;
    for (i = n + 1; i <= lim; i ++)
        if (mvc [i] == 0)
            sol [i - n] += 2;
    ans = 2 * n - ans;
    printf ("%d\n", ans);
    for (i = 1; i <= n; i ++)
        printf ("%d\n", sol [i]);
    return 0;
}