#include <fstream>
#include <iostream>
#include <vector>
#include <cstring>
#define Nmax 10000

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

int left[Nmax], right[Nmax];
bool checked[Nmax], vertexCoverL[Nmax], vertexCoverR[Nmax];
std::vector<int> G[Nmax];

bool match(int node) {

    if (checked[node]) return false;
    checked[node] = true;

    for (int i = 0; i < G[node].size(); i++) {
        int nextNode = G[node][i];
        if (right[nextNode]) continue;

        left[node] = nextNode;
        right[nextNode] = node;
        return true;
    }

    for (int i = 0; i < G[node].size(); i++) {
        int nextNode = G[node][i];

        if (match(right[nextNode])) {
            left[node] = nextNode;
            right[nextNode] = node;
            return true;
        }
    }

    return false;
}

void buildVertexCover(int node) {
    for (int i = 0; i < G[node].size(); i++) {
        int nextNode = G[node][i];
        if (vertexCoverR[nextNode]) continue;

        vertexCoverL[right[nextNode]] = false;
        vertexCoverR[nextNode] = true;
        buildVertexCover(right[nextNode]);
    }
}

int main() {
    int N, M;
    in >> N >> M;

    for (int i = 1; i <= M; i++) {
        int x, y;

        in >> x >> y;
        G[x].push_back(y);
    }

    bool ok = true;
    while (ok) {
        ok = false;
        memset(checked, false, sizeof(checked));

        for (int i = 1; i <= N; i++)
            if (!left[i]) ok = ok | match(i);
    }

    int maxMatch = 0;
    for (int i = 1; i <= N; i++)
        if (left[i]) {
            maxMatch++;
            vertexCoverL[i] = true;
        }

    for (int i = 1; i <= N; i++)
        if (!vertexCoverL[i]) buildVertexCover(i);

    out << 2 * N - maxMatch << "\n";

    for (int i = 1; i <= N; i++) {
        int result = 0;
        if (!vertexCoverL[i]) result++;
        if (!vertexCoverR[i]) result += 2;

        out << result << "\n";
    }
}