#include<fstream>
#include<vector>

using namespace std;

#define NMAX 8193

ifstream fi("felinare.in");
ofstream fo("felinare.out");

int n,m,x,y,i,nc;
vector<int> v[NMAX];
int l[NMAX],r[NMAX],s[2][NMAX];
bool used[NMAX];
bool change;

bool pairup(int k) {
  if(used[k]) return false;
  used[k]=true;
  unsigned int i;
  for(i=0;i<v[k].size();++i)
   if(!r[v[k][i]]) {
     l[k]=v[k][i];
     r[v[k][i]]=k;
     return true;
   }
  for(i=0;i<v[k].size();++i)
   if(pairup(r[v[k][i]])) {
     l[k]=v[k][i];
     r[v[k][i]]=k;
     return true;
   }
  return false;
}

void calc(int k) {
  unsigned int i;
  for(i=0;i<v[k].size();++i)
   if(!s[1][v[k][i]]) {
     s[1][v[k][i]]=1;
     s[0][r[v[k][i]]]=0;
     calc(r[v[k][i]]);
   }
}

int main() {
  fi>>n>>m;
  while(m--) {
    fi>>x>>y;
    v[x].push_back(y);
  }
  do {
    change=false;
    for(i=1;i<=n;++i) used[i]=false;
    for(i=1;i<=n;++i)
     if(!l[i])
      if(pairup(i)) change=true;
  } while(change);
  for(i=1;i<=n;++i)
   if(l[i]) {
     s[0][i]=1;
     ++nc;
   }
  for(i=1;i<=n;++i)
   if(!l[i]) calc(i);
  fo<<2*n-nc<<"\n";
  for(i=1;i<=n;++i) fo<<3-(s[0][i]+(s[1][i]<<1))<<"\n";
  return 0;
}