#include <fstream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
using namespace std;

ifstream cin("felinare.in");
ofstream cout("felinare.out");

const int NMAX=8195;

int n, m;
vector<int> adj[NMAX];
vector<int> l(NMAX), r(NMAX), gl(NMAX), gr(NMAX), viz(NMAX);

bool try_kuhn(int u){
    if(viz[u])return false;
    viz[u]=true;
    for(int v:adj[u]){
        if(l[v]==0||try_kuhn(l[v])){
            l[v]=u;
            r[u]=v;
            gl[u]=1;
            return true;
        }
    }
    return false;
}

int matching(){
    bool ok=1;
    int ans=0;
    while(ok){
        ok=0;
        viz.assign(n+1, 0);
        for(int i=1;i<=n;i++){
            if(!r[i]&&try_kuhn(i)){
                ok=1;
                ans++;
            }
        }
    }
    return ans;
}

void suport(int u){
    for(int v:adj[u]){
        if(!gr[v]){
            gr[v]=1;
            gl[l[v]]=0;
            suport(l[v]);
        }
    }
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x, y;
        cin>>x>>y;
        adj[x].push_back(y);
    }
    cout<<2*n-matching()<<'\n';
    for(int i=1;i<=n;i++){
        if(!gl[i])suport(i);
    }
    for(int i=1;i<=n;i++){
        cout<<3-gl[i]-2*gr[i]<<'\n';
    }
}