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

using namespace std;
typedef int var;

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

#define MAXN 10000

var L[MAXN], R[MAXN];
vector<var> G[MAXN];
bool VIZ[MAXN];
bool SL[MAXN], SR[MAXN];
var n;

bool matchup(var node) {
    if(VIZ[node]) return false;
    VIZ[node] = 1;
    for(auto vec : G[node]) {
        if(!L[vec]) {
            R[node] = vec;
            L[vec] = node;
            return true;
        }
    }
    for(auto vec : G[node]) {
        if(matchup(L[vec])) {
            R[node] = vec;
            L[vec] = node;
            return true;
        }
    }

    return false;
}



void suport(var node) {
    for(auto vec : G[node]) {
        if(!SR[vec]) {
            SR[vec] = 1;
            SL[L[vec]] = 0;
            suport(L[vec]);
        }
    }
}


var solve() {
    bool ok = 1;
    while(ok) {

        memset(VIZ, 0, sizeof(VIZ));
        ok = 0;
        for(var i=1; i<=n; i++) {
            if(!R[i]) {
                ok |= matchup(i);
            }
        }
    }

    var cup = 0;
    for(var i=1; i<=n; i++) {
        if(R[i]) {
            SL[i] = 1;
            cup ++;
        }
    }

    for(var i=1; i<=n; i++) {
        if(!R[i])
            suport(i);
    }

    return cup;
}

int main() {

    var m, a, b;

    fin>>n>>m;
    while(m--) {
        fin>>a>>b;
        G[a].push_back(b);
    }

    fout<<2*n - solve()<<'\n';

    for(var i=1; i<=n; i++) {
        var val = 2*(SR[i]^1) + (SL[i]^1);
        fout<<val<<'\n';
    }

    return 0;
}