#include <stdio.h>
struct nod
{
       int nr;
       nod *adr;
};
int n,m,i,a,b,t[8200],st[8200],dr[8200],k,s[8200],s2[8200],card;
nod *v[8200],*u;
int pairup(int node)
{
    nod *j;
    if (t[node]==1)
       return 0;
    t[node]=1;
    for (j=v[node];j!=NULL;j=j->adr)
        if (dr[j->nr]==0)
        {
           st[node]=j->nr;
           dr[j->nr]=node;
           return 1;
        }
    for (j=v[node];j!=NULL;j=j->adr)
        if (pairup(dr[j->nr]))
        {
           st[node]=j->nr;
           dr[j->nr]=node;
           return 1;
        }
    return 0;
}
void calc(int node)
{
     nod *j;
     for (j=v[node];j!=NULL;j=j->adr)
         if (s2[j->nr]==0)
         {
            s2[j->nr]=1;
            s[dr[j->nr]]=0;
            calc(dr[j->nr]);
         }
}
int main()
{
    freopen("felinare.in","r",stdin);
    freopen("felinare.out","w",stdout);
    scanf("%d %d",&n,&m);
    while (m--)
    {
          scanf("%d %d",&a,&b);
          if (v[a]==NULL)
          {
             v[a]=new nod;
             v[a]->nr=b;
             v[a]->adr=NULL;
          }
          else
          {
              u=new nod;
              u->nr=b;
              u->adr=v[a];
              v[a]=u;
          }
    }
    do
    {
      k=1;
      for (i=1;i<=n;++i)
          t[i]=0;
      for (i=1;i<=n;++i)
          if (st[i]==0)
             if (pairup(i)==1)
                k=0;
    }
    while (k==0);
    for (i=1;i<=n;++i)
        if (st[i]!=0)
        {
           s[i]=1;
           ++card;
        }
    for (i=1;i<=n;++i)
        if (st[i]==0)
           calc(i);
    printf("%d\n",2*n-card);
    for (i=1;i<=n;++i)
        if (s[i]==1 && s2[i]==1)
           printf("%d\n",0);
        else
            if (s[i]==1 && s2[i]==0)
               printf("%d\n",2);
            else
                if (s[i]==0 && s2[i]==1)
                   printf("%d\n",1);
                else
                    printf("%d\n",3);
    return 0;
}