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

using namespace std;

vector<int> G[17000];

int l[17000], r[17000];
bool used[17000];

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

    used[nod] = true;

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

            return true;
        }
    }

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

            return true;
        }
    }

    return false;
}

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 + n);
        G[a + n].push_back(b + n);
        G[a + n].push_back(b);
    }

    for (int i = 1; i <= n; ++i) {
        G[i].push_back(i + n);
    }

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

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

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

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

    g << nrMax << "\n";

    for (int i = 1; i <= n; ++i) {
        if (l[i] && l[i + n]) {
            g << 3 << "\n";
        }
        else if (l[i]) {
            g << 2 << "\n";
        }
        else if (l[i + n]) {
            g << 1 << "\n";
        }
        else {
            g << 0 << "\n";
        }
    }

    return 0;
}