#include <stdio.h>
#include <string.h>
#define MAXN 8191
#define MAXM 20000
int n, m, val[2*MAXM+1], next[2*MAXM+1], lista[MAXN+1], last[MAXN+1], baiat[MAXN+1], fata[MAXN+1], v[MAXN+1];
char viz[MAXN+1], vizf[MAXN+1], vizb[MAXN+1];
inline void adauga(int x, int y){
    val[++m]=y;
    next[m]=last[x];
    last[x]=m;
}
int gasim(int x){
    if(viz[x]==1){
        return 0;
    }
    viz[x]=1;
    int p=lista[x];
    while(p){
        if(baiat[val[p]]==0){
            baiat[val[p]]=x;
            fata[x]=val[p];
            return 1;
        }
        p=next[p];
    }
    p=lista[x];
    while(p){
        if(gasim(baiat[val[p]])){
            baiat[val[p]]=x;
            fata[x]=val[p];
            return 1;
        }
        p=next[p];
    }
    return 0;
}
inline void cuplaj(){
    int i, f;
    f=1;
    while(f){
        f=0;
        memset(viz, 0, sizeof viz);
        for(i=1; i<=n; i++){
            if(fata[i]==0){
                if(gasim(i)){
                    f=1;
                }
            }
        }
    }
}
void alternant(int x){
    vizf[x]=1;
    int p=last[x];
    while(p){
        if(vizb[val[p]]==0){
            vizb[val[p]]=1;
            if(vizf[fata[val[p]]]==0){
                alternant(fata[val[p]]);
            }
        }
        p=next[p];
    }
}
inline void suport(){
    int i, p;
    for(i=1; i<=n; i++){
        p=lista[i];
        while(p){
            if(val[p]!=fata[i]){
                adauga(val[p], i);
            }
            p=next[p];
        }
    }
    for(i=1; i<=n; i++){
        if((baiat[i]==0)&&(vizf[i]==0)){
            alternant(i);
        }
    }
}
int main(){
    int ans, i, x;
    FILE *fin, *fout;
    fin=fopen("felinare.in", "r");
    fout=fopen("felinare.out", "w");
    fscanf(fin, "%d%d", &n, &m);
    for(i=1; i<=m; i++){
        fscanf(fin, "%d%d", &x, &val[i]);
        next[i]=lista[x];
        lista[x]=i;
    }
    cuplaj();
    suport();
    ans=0;
    for(i=1; i<=n; i++){
        if(vizf[i]==1){//nu apare in suport
            v[i]+=2;
            ans++;
        }
        if(vizb[i]==0){//nu apare in suport
            v[i]++;
            ans++;
        }
    }
    fprintf(fout, "%d\n", ans);
    for(i=1; i<=n; i++){
        fprintf(fout, "%d\n", v[i]);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}