//
// 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;
}

int out[NMAX + 2], in[NMAX + 2];
bool outOn[NMAX + 2], inOn[NMAX + 2];

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

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

        out[x]++;
        in[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(out[i] == 0 || l[i] != 0) {
            outOn[i] = true;
        }
        if(in[i] == 0 || r[i] == 0) {
            inOn[i] = true;
        }

        if(!inOn[i] && !outOn[i]) {
            cout << 0 << '\n';
        } else if(outOn[i] && !inOn[i]) {
            cout << 1 << '\n';
        } else if(inOn[i] && !outOn[i]) {
            cout << 2 << '\n';
        } else {
            cout << 3 << '\n';
        }
    }

    return 0;
}