#include <stdio.h>
#define MAXN 8191
#define MAXM 20000
int ult[MAXN], next[MAXM], nod[MAXM];
char tr[MAXN];
int pairst[MAXN], pairdr[MAXN];
int fel[MAXN];
int n;

int augm(int dist, int x){
  if(dist & 1){
    if(tr[x + n])
      return 0;
    tr[x + n] = 1;
    return augm(dist + 1, pairdr[x]);
  }
  else{
    if(tr[x])
      return 0;
    tr[x] = 1;
    int poz;
    poz = ult[x];
    while(poz != -1){
      if(pairdr[nod[poz]] == -1){
        pairst[x] = nod[poz];
        pairdr[nod[poz]] = x;
        return 1;
      }
      poz = next[poz];
    }
    poz = ult[x];
    while(poz != -1){
      if(augm(dist + 1, nod[poz])){
        pairst[x] = nod[poz];
        pairdr[nod[poz]] = x;
        return 1;
      }
      poz = next[poz];
    }
    return 0;
  }
}

int main(){
  FILE *in = fopen("felinare.in", "r");
  int m, i, dr = 0, x, y;
  fscanf(in, "%d%d", &n, &m);
  for(i = 0; i < n; i++){
    pairst[i] = pairdr[i] = -1;
    ult[i] = -1;
    fel[i] = 3;
  }
  for(i = 0; i < m; i++){
    fscanf(in, "%d%d", &x, &y);
    x--;  y--;
    nod[dr] = y;
    next[dr] = ult[x];
    ult[x] = dr;
    dr++;
  }
  fclose(in);
  char aux = 1;
  while(aux){
    aux = 0;
    for(i = 0; i < n; i++)
      if(pairst[i] == -1 && augm(0, i))
        aux = 1;
    memset(tr, 0, sizeof tr);
  }
  for(i = 0; i < n; i++)
    if(pairst[i] == -1)
      augm(0, i);
  int nr = 2 * n;
  for(i = 0; i < n; i++){
    if(!tr[i]){
      fel[i] -= 1;
      nr--;
    }
  }
  for(i = 0; i < n; i++){
    if(tr[i + n]){
      fel[i] -= 2;
      nr--;
    }
  }
  FILE *out = fopen("felinare.out", "w");
  fprintf(out, "%d\n", nr);
  for(i = 0; i < n; i++)
    fprintf(out, "%d\n", fel[i]);
  fclose(out);
  return 0;
}