#include<fstream.h>
ifstream fin("felinare.in");
ofstream fout("felinare.out");

struct nod
{int val,m;
nod * urm;
}*a[8192],*b[8192];

int n,m,gr1[8192],gr2[8192],s[8192],v[20001],g1[8192],g2[8192],nr,s1[8192],s2[8192];

void adauga(int x,int y,int i,nod *c[8192])
{nod *p;
p=new nod;
p->val=y;
p->m=i;
p->urm=c[x];
c[x]=p;
}

int valid(int i,int j)
{nod *p;
 if(i==1)
  {for(p=a[j];p!=NULL;p=p->urm)
    if(v[p->m]==1) return 0;
  }
 else
  {for(p=b[j];p!=NULL;p=p->urm)
    if(v[p->m]==1) return 0;
  }
 return 1;
}

void aprinde(int i,int j)
{if(s[j]==0) s[j]=i;
 if(s[j]!=i) s[j]=3;
 if(i==1)
  for(nod *p=a[j];p!=NULL;p=p->urm) v[p->m]++;
 else
  for(nod *p=b[j];p!=NULL;p=p->urm) v[p->m]++;
 nr++;
}

int main()
{fin>>n>>m;
int i,j,x,y,min;
for(i=1;i<=m;i++)
 {fin>>x>>y;
  adauga(x,y,i,a);
  adauga(y,x,i,b);
  g1[x]++;
  g2[y]++;
 }
for(i=1;i<=n;i++)
 {x=n+1;
  y=n+1;
  for(j=1;j<=n;j++)
   {if(!s1[j] && x>g1[j])
     {gr1[i]=j;
      x=g1[j];
     }
    if(!s2[j] && y>g2[j])
     {gr2[i]=j;
      y=g2[j];
     }
   }
  s1[gr1[i]]=1;
  s2[gr2[i]]=1;
 }
i=j=1;
while(i<=n && j<=n)
 {if(g1[gr1[i]]<=g2[gr2[j]])
   {if(valid(1,gr1[i])) aprinde(1,gr1[i]);
    i++;
   }
  else
   {if(valid(2,gr2[j])) aprinde(2,gr2[j]);
    j++;
   }
 }
while(i<=n)
 {if(valid(1,gr1[i])) aprinde(1,gr1[i]);
  i++;
 }
while(j<=n)
 {if(valid(2,gr2[j])) aprinde(2,gr2[j]);
  j++;
 }
fout<<nr<<"\n";
for(i=1;i<=n;i++) fout<<s[i]<<"\n";
fin.close();
fout.close();
return 0;
}