#include <stdio.h>
#include <string.h>
#define NM 8192
struct ch {int nod;ch *urm;} *g[NM*2];
int n,m,c[NM*2],cmax;
int viz[NM];
int cupleaza(int k)
{ch *p;
 if (viz[k]==1) return 0;
 viz[k]=1;
 for (p=g[k];p;p=p->urm)
        if (!c[p->nod]||cupleaza(c[p->nod]))
                {c[p->nod]=k;
                 c[k]=p->nod;
                 return 1;
                }
 return 0;
}
void cuplaj()
{int i;cmax=0;
 for (i=1;i<=n;i++)
        {if (c[i]) {cmax++;continue;}
         if (cupleaza(i)) cmax++;
         else
                {memset(viz,0,sizeof(viz));
                 if (cupleaza(i)) cmax++;
                }
        }
}
////////////////////////////////////////
inline void add(int x,int y)
{ch *p=new ch;
 p->nod=y;
 p->urm=g[x];
 g[x]=p;
}
/////////////////////////////////////////
void dfs(int k)
{ch *p;
 viz[k]=1;
 for (p=g[k];p;p=p->urm)
        if (!viz[p->nod]&&c[p->nod]!=k) dfs(p->nod);
}
int main()
{freopen("felinare.in","r",stdin);
 freopen("felinare.out","w",stdout);
 scanf("%d %d",&n,&m);
 int x,y,i;
 while (m--)
        {scanf("%d %d",&x,&y);
         add(x,y+n);
         add(y+n,x);
        }
 cuplaj();
 printf("%d\n",2*n-cmax);
 memset(viz,0,sizeof(viz));
 for (i=1;i<=n;i++)
        if (!viz[i]&&!c[i]) dfs(i);
 int sw1,sw2;
 for (i=1;i<=n;i++)
        {sw1=0;sw2=0;
         if (c[i]&&!viz[i]) sw1=1;
         if (c[i]&&viz[i]) sw2=1;
         printf("%d\n",3-(sw2+2*sw1));
        }
 return 0;
}