#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>

std::ifstream fin("felinare.in");
std::ofstream fout("felinare.out");

#define MAXN 10000

int N, M, used[MAXN], left[MAXN], right[MAXN], p[MAXN], rez[MAXN];
std::vector<int> graph[MAXN];

bool doCuplaj(int nod) {
    if (used[nod]) return 0;
    used[nod] = 1;

    for (int i = 0; i < graph[nod].size(); ++i) {
        int node = graph[nod][i];
        if (!right[node] || doCuplaj(right[node])) {
            right[node] = nod;
            left[nod] = node;
            return 1;
        }
    }

    return 0;
}

void vertex_cover(int nod) {
    for (int i = 0; i < graph[nod].size(); ++i) {
        int node = graph[nod][i];

        if (!p[node + N]) {
            p[node + N] = 1;
            p[right[node]] = 0;
            vertex_cover(right[node]);
        }
    }
}

void do_vertex_cover() {
    for (int i = 1; i <= N; ++i)
        if (left[i])
            p[i] = 1;

    for (int i = 1; i <= N; ++i)
        if (!left[i])
            vertex_cover(i);

    for (int i = 1; i <= N; ++i) {
        rez[i] = 3;
        if (p[i])
            --rez[i];
        if (p[i + N])
            rez[i] -= 2;
    }
}

int main() {
    fin >> N >> M;

    for (int i = 1; i <= M; ++i) {
        int x, y;
        fin >> x >> y;
        graph[x].push_back(y);
    }

    int ok = 1, sol = 0;
    while (ok) {
        ok = 0;
        memset(used, 0, sizeof(used));

        for (int i = 1; i <= N; ++i)
            if (!used[i] && !left[i]) {
                int a = doCuplaj(i);
                ok |= a;
                sol += a;
            }
    }

    fout << 2 * N - sol << "\n";

    do_vertex_cover();

    for (int i = 1; i <= N; ++i)
        fout << rez[i] << "\n";

    return 0;
}