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

using namespace std;

const int NMAX = 8191;

int N, M, cuplaj;

int cupl1[NMAX + 1], cupl2[NMAX + 1];
bool viz[NMAX + 1];

vector<int> v1[NMAX + 1], v2[NMAX + 1];

void citire () {
    int x, y;
    scanf ("%d%d", &N, &M);

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

bool cupleaza (int nod) {
    if (viz[nod])
        return false;
    viz[nod] = true;

    for (int i = 0; i < v1[nod].size (); ++i) {
        int csp = v1[nod][i];

        if (!cupl2[csp]) {
            cupl1[nod] = csp;
            cupl2[csp] = nod;

            ++cuplaj;
            return true;
        }
    }

    for (int i = 0; i < v1[nod].size (); ++i) {
        int csp = v1[nod][i];

        if (cupleaza(cupl2[csp])) {
            cupl1[nod] = csp;
            cupl2[csp] = nod;

            return true;
        }
    }

    return false;
}

void rezolva () {
    bool ok;

    do {
        ok = false;
        memset (viz, 0, sizeof (viz));

        for (int i = 1; i <= N; ++i)
            if (!cupl1[i])
                ok |= cupleaza (i);
    } while (ok);

    printf ("%d\n", 2 * N - cuplaj);

    for (int i = 1; i <= N; ++i) {
        if (cupl1[i]) {
            if (cupl2[i])
                printf ("3\n");
            else
                printf ("1\n");
        } else if (cupl2[i])
            printf ("2\n");
        else
            printf ("0\n");
    }
}

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

    citire ();

    rezolva ();

    return 0;
}