//
// Created by mihai145 on 05.03.2021.
//

#include <fstream>
#include <vector>

using namespace std;

ifstream cin("felinare.in");
ofstream cout("felinare.out");

const int NMAX = 9000;

int N, M;
vector<int> g[NMAX + 2];

int matching;
int l[NMAX + 2], r[NMAX + 2];
bool d[NMAX + 2];

bool PairUp(int node) {
    if(d[node]) {
        return false;
    }

    d[node] = true;

    for(int it : g[node]) {
        if(!r[it]) {
            ++matching;
            r[it] = node;
            l[node] = it;
            return true;
        }
    }

    for(int it : g[node]) {
        if(PairUp(r[it])) {
            r[it] = node;
            l[node] = it;
            return true;
        }
    }

    return false;
}

bool leftSeen[NMAX + 2], rightSeen[NMAX + 2];

void dfs(int node) {
    leftSeen[node] = true;

    for(int son : g[node]) {
        if(r[son] != 0) {
            rightSeen[son] = true;
            dfs(r[son]);
        }
    }
}

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

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

    bool ok = false;
    do {
        ok = false;

        for(int i = 1; i <= N; i++) {
            d[i] = false;
        }

        for(int i = 1; i <= N; i++) {
            if(!l[i]) {
                ok |= PairUp(i);
            }
        }
    } while(ok);

    int maxIndepSet = 2 * N - matching;
    cout << maxIndepSet << '\n';

    for(int i = 1; i <= N; i++) {
        if(!l[i]) {
            dfs(i);
        }
    }

    for(int i = 1; i <= N; i++) {
        if(!leftSeen[i] && rightSeen[i]) {
            cout << 0 << '\n';
        } else if(leftSeen[i] && rightSeen[i]) {
            cout << 1 << '\n';
        } else if(!leftSeen[i] && !rightSeen[i]) {
            cout << 2 << '\n';
        } else {
            cout << 3 << '\n';
        }
    }

    return 0;
}