#include<stdio.h>
#define N 10005
int n,m,l[N],r[N],sl[N],sr[N],u[N];
int i,j,k,cup,ok;
typedef struct NOD {
    int vf;
    NOD* urm;
}*PNOD;
PNOD g[N];   
void Add(int i, int j){   
    PNOD q=new NOD;
    q->vf=j;
    q->urm=g[i];
    g[i]=q;
}
int fel(int nod){
    if(u[nod])
		return 0;
    u[nod] = 1;
    PNOD q;
    for(q=g[nod];q;q=q->urm)
        if(r[q->vf]==-1){
            r[q->vf]=nod;
            l[nod]=q->vf;
            sl[nod]=1;
            return 1;
        }
    for(q=g[nod];q;q=q->urm)
        if(fel(r[q->vf])){
            r[q->vf]=nod;
            l[nod]=q->vf;
            sl[nod]=1;
            return 1;
        }
    return 0;
}
void sup(int nod){
    for(PNOD q=g[nod];q;q=q->urm)
        if(!sr[q->vf])
            sr[q->vf]=1,sl[r[q->vf]] = 0,sup(r[q->vf]); 
}
void bip(){
    int i;
    for(i=1;i<=n;++i)
        l[i]=r[i]=-1, u[i]=0;
    for(ok=1;ok;){
        for(i=0;i<=n;u[i]=0,++i);
        for(ok=0,i=1;i<=n;++i)
            if(l[i]==-1&&fel(i))
                cup++,ok=1;
    }
    for(i=1;i<=n;++i)
        if(!sl[i])
            sup(i);
}
int main(){
    freopen("felinare.in", "r", stdin);
    freopen("felinare.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for(k=1;k<=m;++k)
        scanf("%d %d",&i, &j),Add(i, j);
    bip();
    printf("%d\n",2*n-cup);
    for(i=1;i<=n;++i)
        printf("%d\n",1-sl[i]+2*(1-sr[i]));
    return 0;
}