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

using namespace std;

const int NMAX = 8191;

int N, M, cuplaj;

int cupll[NMAX + 1], cuplr[NMAX + 1];
bool sl[NMAX + 1], sr[NMAX + 1];
bool viz[NMAX + 1];

vector<int> v[NMAX + 1];

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

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

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

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

        if (!cupll[csp]) {
            cuplr[nod] = csp;
            cupll[csp] = nod;
            sl[nod] = true;

            return true;
        }
    }

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

        if (cupleaza(cupll[csp])) {
            cuplr[nod] = csp;
            cupll[csp] = nod;
            sl[nod] = true;

            return true;
        }
    }

    return false;
}

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

        if (!sr[csp]) {
            sr[csp] = true;
            sl[cupll[csp]] = false;

            ilum (cupll[csp]);
        }
    }
}

void rezolva () {
    for (int i = 1; i <= N; ++i) {
        if (!cupleaza (i)) {
            memset (viz, 0, sizeof (viz));
            cuplaj += cupleaza (i);
        } else
            ++cuplaj;
    }

    for (int i = 1; i <= N; ++i)
        if (!sl[i])
            ilum (i);
}

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

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

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

    citire ();

    rezolva ();

    afisare ();

    return 0;
}