#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> G[8200];

int l[8200], r[8200];
int sl[8200], sr[8200];
bool used[8200];

bool bpMatch(int nod) {
    if (used[nod]) {
        return false;
    }

    used[nod] = true;

    for (int dest: G[nod]) {
        if (!l[dest]) {
            r[nod] = dest;
            l[dest] = nod;

            sl[nod] = 1;

            return true;
        }
    }

    for (int dest: G[nod]) {
        if (bpMatch(l[dest])) {
            r[nod] = dest;
            l[dest] = nod;

            sl[nod] = 1;

            return true;
        }
    }

    return false;
}

void support(int nod) {
    for (int dest: G[nod]) {
        if (!sr[dest]) {
            sr[dest] = 1;
            sl[l[dest]] = 0;
            support(l[dest]);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    ifstream f("felinare.in");
    ofstream g("felinare.out");

    int n, m;
    f >> n >> m;
    int a, b;
    for (int i = 1; i <= m; ++i) { // (1, n) - out | (n + 1, 2 * n) - in
        f >> a >> b;
        G[a].push_back(b);
    }

    for (bool change = true; change; ) {
        change = false;

        for (int i = 1; i <= n; ++i) {
            used[i] = false;
        }

        for (int i = 1; i <= n; ++i) {
            if (!r[i]) {
                change |= bpMatch(i);
            }
        }
    }

    int nrMax = 0;
    for (int i = 1; i <= n; ++i) {
        nrMax += (r[i] != 0);
    }

    g << 2 * n - nrMax << "\n";

    for (int i = 1; i <= n; ++i) {
        if (!sl[i]) {
            support(i);
        }
    }

    for (int i = 1; i <= n; ++i) {
        g << 1 - sl[i] + 2 * (1 - sr[i]) << "\n";
    }

    return 0;
}