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

using namespace std;

const int nmax = 8192;

int n, m;
vector<int> A[nmax];
int L[nmax];
int R[nmax];
int ans[nmax];
int LC[nmax];
int RC[nmax];
int U[nmax];

bool pairup(int x) {
    if (U[x])
        return false;

    U[x] = 1;
    for (int i = 0; i < A[x].size(); i++) {
        int y = A[x][i];

        if (!R[y] || pairup(R[y])) {
            L[x] = y;
            R[y] = x;
            return true;
        }
    }

    return false;
}

void cuplaj() {
    bool tmp = true;

    while (tmp) {
        tmp = false;
        memset(U, 0, sizeof(U));
        for (int i = 1; i <=  n; i++) {
            if (!L[i] && pairup(i)) {
                tmp = true;
            }
        }
    }
}

void bf(int x) {
    for (int i = 0; i < A[x].size(); i++) {
        int y = A[x][i];
        if (!RC[y]) {
            RC[y] = 1;
            LC[R[y]] = 0;
            bf(R[y]);
        }
    }
}

int minvertexcover() {
    for (int i = 1; i <= n; i++) {
        if (L[i] != 0)
            LC[i] = 1;
    }

    for (int i = 1; i <= n; i++) {
        if (L[i] == 0)
            bf(i);
    }


    int num = 0;
    for (int i = 1; i <= n; i++) {
        if (!LC[i]) {
            num++;
            ans[i] |= 1;
        }

        if (!RC[i]) {
            num++;
            ans[i] |= 2;
        }
    }

    return num;
}

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

    scanf("%d %d", &n, &m);

    for (int i = 1, x, y; i <= m; i++) {
        scanf("%d %d", &x, &y);
        A[x].push_back(y);
    }

    cuplaj();
    printf("%d\n", minvertexcover());

    for (int i = 1; i <= n; i++) {
        printf("%d\n", ans[i]);
    }

    return 0;
}