#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

const int NMAX = 8191;

bool viz[NMAX + 5];
bool sl[NMAX + 5], sr[NMAX + 5]; /// pt suportul minim
int n, m, cuplaj;
int l[NMAX + 5], r[NMAX + 5];
vector<int> v[NMAX + 5];

bool alternating_path(int nod) {
  if(viz[nod])
    return false;

  viz[nod] = true;
  for(int vec: v[nod])
    if(!r[vec] || alternating_path(r[vec])) {
      l[nod] = vec;
      r[vec] = nod;
      return true;
    }
  return false;
}

void dfs(int nod) {
  viz[nod] = true;
  sl[nod] = false; /// nod va fi in stanga, e pe un alternating path deci nu face parte din suport
  for(int vec: v[nod]) {
    if(viz[r[vec]])
      continue;
    sr[vec] = true; /// vece pe alternating path, dar e in dreapta, deci face parte din suport
    dfs(r[vec]);
  }
}

int main() {
  freopen("felinare.in", "r", stdin);
  freopen("felinare.out", "w", stdout);

  scanf("%d %d", &n, &m);
  for(int i = 1; i <= m; i++) {
    int x, y;
    scanf("%d %d", &x, &y);
    v[x].push_back(y);
  }

  bool ok;
  do { /// cuplaj
    ok = false;
    for(int i = 1; i <= n; i++)
      viz[i] = false;

    for(int i = 1; i <= n; i++)
      if(!l[i] && alternating_path(i)) {
        ok = true;
        cuplaj++;
      }
  } while(ok);

  for(int i = 1; i <= n; i++)
    if(l[i]) {
      sl[i] = true; /// daca face parte din cuplaj presupunem ca face si din suport
      viz[i] = false;
    }

  for(int i = 1; i <= n; i++) /// caut toate alternating paths care incep din stanga
    if(!l[i]) /// i nu e cuplat
      dfs(i);

  printf("%d\n", 2 * n - cuplaj); /// dim cuplajului = dim suportului
  for(int i = 1; i <= n; i++)
    if(sl[i]) {
      if(sr[i])
        printf("0\n");
      else
        printf("2\n");
    }
    else if(sr[i])
      printf("1\n");
    else
      printf("3\n");

  return 0;
}