#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream f("felinare.in");
ofstream g("felinare.out");

vector <int> v[17005];
int n,m,use[17005],l[17005],r[17005],was[17005],sol,is[17005],gr[17005];

int DFS(int x)
{ int i,nod;
     if (use[x]) return 0;
      use[x]=1;

    for(i=0;i<v[x].size();i++)
    { nod=v[x][i];
       if (!r[nod])
       { l[x]=nod;
         r[nod]=x;
        return 1;
       }
    }

    for(i=0;i<v[x].size();i++)
    { nod=v[x][i];
        if (DFS(r[nod]))
        { l[x]=nod;
          r[nod]=x;
          return 1;
        }
    }

 return 0;
}
 void Suport(int x)
 { int i;
    for(i=0;i<v[x].size();i++)
     if (!was[v[x][i]])
     {
         was[v[x][i]]=1;
         is[v[x][i]]=0;
        Suport(r[v[x][i]]);
     }
 }
int main()
{ int i,x,y,ok;
  f>>n>>m;

  for(i=1;i<=m;i++)
  { f>>x>>y;
     v[n+x].push_back(y);
     gr[n+x]++; gr[y]++;
  }

  ok=1;

  while(ok)
  { memset(use,0,sizeof(use));
    ok=0;
    for(i=n+1;i<=2*n;i++)
     if (!l[i] && DFS(i)) {sol++; ok=1;}
  }

    for(i=1;i<=2*n;i++)
     if (!l[i]) is[i]=1;


    for(i=1;i<=2*n;i++)
      if (!l[i]) Suport(i);


     g<<2*n-sol<<"\n";

     for(i=1;i<=n;i++)
     {
        if (is[i] && is[n+i]) g<<"3"<<"\n";
        if (is[i] && !is[n+i]) g<<"2"<<"\n";
        if (!is[i] && is[n+i]) g<<"1"<<"\n";
        if (!is[i] && !is[n+i]) g<<"0"<<"\n";
     }

    return 0;
}