#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream si("felinare.in");
ofstream so("felinare.out");
int u[8195], l[8195], r[8195], z[8195];
vector<int> v[8195];
bool augment(int n) {
    if(u[n])
        return false;
    u[n]=1;
    for(int i=0; i<v[n].size(); ++i) {
        if(!r[v[n][i]]) {
            l[n]=v[n][i];
            r[v[n][i]]=n;
            return true;
        }
    }
    for(int i=0; i<v[n].size(); ++i) {
        if(augment(r[v[n][i]])) {
            l[n]=v[n][i];
            r[v[n][i]]=n;
            return true;
        }
    }
    return false;

}
void path(int n) {
    if(u[n])
        return;
    u[n]=1;
    for(int i=0; i<v[n].size(); ++i) {
        if(l[n]!=v[n][i]&&z[v[n][i]]==0) {
            z[v[n][i]]=1;
            path(r[v[n][i]]);
        }
    }
}
int main() {
    int n, m;
    si>>n>>m;
    for(int i=1; i<=m; ++i) {
        int a, b;
        si>>a>>b;
        v[a].push_back(b);
    }
    bool ok=true;
    while(ok) {
        ok=false;
        memset(u, 0, sizeof(u));
        for(int i=1; i<=n; ++i) {
            if(!l[i]) {
                ok|=augment(i);
            }
        }
    }
    memset(u, 0, sizeof(u));
    int nr=0;
    for(int i=1; i<=n; ++i) {
        if(l[i]==0) {
            path(i);
        }
        else
            nr++;
    }
    so<<n*2-nr<<'\n';
    for(int i=1; i<=n; ++i) {
        int val=0;
        if(z[i]==0) {
            val+=2;
        }
        if(u[i])
            val++;
        so<<val<<'\n';
    }
    return 0;
}