#include <bits/stdc++.h>

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

class BipMatching {
    std::vector<int> pairs;
    std::vector<std::vector<int>> edges;

    bool tryPairup(std::vector<bool> &used, int node) {
        if (used[node]) return false;
        used[node] = true;
        for (int edge : edges[node]) {
            if (pairs[edge] == -1) {
                pairs[edge] = node;
                pairs[node] = edge;
                return true;
            }
        }
        for (int edge : edges[node]) {
            if (tryPairup(used, pairs[edge])) {
                pairs[edge] = node;
                pairs[node] = edge;
                return true;
            }
        }
        return false;
    }

    void cover(std::vector<bool> &viz, int node) {
        if (viz[node]) return;
        viz[node] = true;
        for (int edge : edges[node]) {
            if (!viz[edge] && pairs[edge] != node) {
                viz[edge] = true;
                if (pairs[edge] != -1) {
                    cover(viz, pairs[edge]);
                }
            }
        }
    }

public:
    BipMatching(int n) : pairs(n, -1), edges(n) {}

    void addEdge(int u, int v) {
        edges[u].push_back(v);
    }

    void match() {
        std::vector<bool> used(pairs.size());
        bool ok = false;
        do {
            ok = false;
            for (int i = 0; i < used.size(); i++) {
                used[i] = false;
            }
            for (int i = 0; i < pairs.size(); i++) {
                if (pairs[i] == -1) {
                    ok |= tryPairup(used, i);
                }
            }
        } while (ok);
    }

    int countMatched() {
        int matched = 0;
        for (int p : pairs) {
            if (p != -1) matched++;
        }
        return matched;
    }

    std::vector<int> findCover(int leftUpTo) {
        std::vector<bool> viz(pairs.size());
        for (int i = 0; i < leftUpTo; i++) {
            if (pairs[i] == -1) {
                cover(viz, i);
            }
        }
        std::vector<int> covered;
        covered.reserve(pairs.size());
        for (int i = 0; i < leftUpTo; i++) {
            if (!viz[i]) {
                covered.push_back(i);
            }
        }
        for (int i = leftUpTo; i < pairs.size(); i++) {
            if (viz[i]) covered.push_back(i);
        }
        return covered;
    }
};

int main() {
    int n, m;
    fin >> n >> m;

    BipMatching matching(2 * n);

    for (int i = 0; i < m; i++) {
        int a, b;
        fin >> a >> b;
        a--, b--;
        matching.addEdge(a, n + b);
    }

    matching.match();

    auto cover = matching.findCover(n);

    fout << 2 * n - cover.size() << '\n';

    std::vector<bool> on(2 * n, true);
    for (int c : cover) on[c] = false;

    for (int i = 0; i < n; i++) {
        int u = i, v = n + i;
        int res;
        if (!on[u] && !on[v]) {
            res = 0;
        } else if (on[u] && !on[v]) {
            res = 1;
        } else if (!on[u] && on[v]) {
            res = 2;
        } else {
            res = 3;
        }
        fout << res << '\n';
    }
}