#include <fstream>
#include <bitset>
#include <vector>

using namespace std;

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

const int NMAX = 8192;

int n, m, cuplaj;

bitset<NMAX> viz, vizL, vizR;
int l[NMAX], r[NMAX];

vector<int> G[NMAX];

void citire() {
    fin >> n >> m;
    for(int i = 1, x, y; i <= m; ++i) {
        fin >> x >> y;
        G[x].push_back(y);
    }
}

bool dfs(int x) {
    if(viz[x]) return 0;
    viz[x] = 1;

    for(const auto& y : G[x]) {
        if(!r[y] || dfs(r[y])) {
            l[x] = y;
            r[y] = x;
            return 1;
        }
    }
    return 0;
}

void karp() {
    bool amSchimbat;

    do {
        amSchimbat = 0;
        viz.reset();

        for(int i = 1; i <= n; ++i) {
            if(!l[i] && dfs(i)) {
                amSchimbat = 1;
                ++cuplaj;
            }
        }
    } while(amSchimbat);
}

void dfsReconstructie(int x) {
    vizL[x] = 1;

    for(int y : G[x]) {
        if(l[x] == y) continue;
        if(vizR[y]) continue;

        vizR[y] = 1;
        if(r[y] && !vizL[r[y]]) {
            dfsReconstructie(r[y]);
        }
    }
}

void reconstructie() {
    for(int i = 1; i <= n; ++i) {
        if(!l[i] && !vizL[i]) {
            dfsReconstructie(i);
        }
    }
}

void afis() {
    fout << 2 * n - cuplaj << '\n';
    for(int i = 1; i <= n; ++i) {
        if(vizL[i] && vizR[i]) {
            fout << "0\n";
        } else if(vizR[i]) {
            fout << "1\n";
        } else if(vizL[i]) {
            fout << "2\n";
        } else {
            fout << "3\n";
        }
    }
}

int main() {
    citire();
    karp();
    reconstructie();
    afis();
    return 0;
}