#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

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

const int maxn = 8200;

int n, m, i, x, y;
vector <int> nod[maxn];
int lga[maxn], lgb[maxn], l[maxn], r[maxn];
int viz[maxn], ans;

bool match(int x) {
    if(viz[x] == 1) {
        return false;
    }
    viz[x] = 1;
    for(auto u : nod[x]) {
        if(l[u] == false) {
            l[u] = x;
            r[x] = u;
            return true;
        }
    }
    for(auto u : nod[x]) {
        if(match(l[u]) == true) {
            l[u] = x;
            r[x] = u;
            return true;
        }
    }
    return false;
}

void dfs(int x) {
    for(auto u : nod[x]) {
        if(lgb[u] == false) {
            lgb[u] = true;
            dfs(l[u]);
        }
    }

}

int main()
{
    f >> n >> m;
    for(i = 1; i <= m; i ++) {
        f >> x >> y;
        nod[x].push_back(y);
    }
    bool ok = false;
    do {
        ok = false;
        memset(viz, 0, sizeof(viz));

        for(i = 1; i <= n; i ++) {
            if(r[i] == 0 && match(i) == true) {
                ans++;
                ok = true;
            }
        }

    } while(ok == true);

    for(i = 1; i <= n; i ++) {
        if(r[i] == 0) {
            dfs(i);
        }
    }
    for(i = 1; i <= n; i ++) {
        if(r[i] != 0 && lgb[r[i]] == false) {
            lga[i] = true;
        }
    }

    g << 2 * n - ans << '\n';
    for(i = 1; i <= n; i ++) {
        if(lga[i] == true && lgb[i] == true) {
            g << "0\n";
        } else
        if(lga[i] == false && lgb[i] == true) {
            g << "1\n";
        } else
        if(lga[i] == true && lgb[i] == false) {
            g << "2\n";
        } else {
            g << "3\n";
        }
    }

    f.close(); g.close();
    return 0;
}