#include <cstdio>
#include <cstring>

using namespace std;

constexpr int maxN = (1 << 13);
constexpr int maxM = 20000;
constexpr int NIL = -1;

struct Edge {
  int v;
  int next;
} G[maxM];

int head[maxN];

int l[maxN], r[maxN];
bool color[maxN];
bool supportColor[2][maxN];

bool pairUp( const int node ) {
  if (color[node])
    return false;
  color[node] = true;
  for (int i = head[node]; i != NIL; i = G[i].next) {
    const int to = G[i].v;
    if (r[to] == NIL) {
      l[node] = to;
      r[to] = node;
      return true;
    }
  }
  for (int i = head[node]; i != NIL; i = G[i].next) {
    const int to = G[i].v;
    if (pairUp(r[to])) {
      l[node] = to;
      r[to] = node;
      return true;
    }
  }
  return false;
}

int findMatching( const int n ) {
  memset(l, NIL, 4 * n);
  memset(r, NIL, 4 * n);

  bool changed;
  do {
    memset(color, 0, n);
    changed = false;
    for (int i = 0; i < n; i++)
      if (l[i] == NIL)
        changed |= pairUp(i);
  } while (changed);

  int matching = 0;
  for (int i = 0; i < n; i++)
    if (l[i] != NIL) {
      matching++;
    }
  return matching; 
}

void supportPairUp( const int node ) {
  for (int i = head[node]; i != NIL; i = G[i].next) {
    const int to = G[i].v;
    if (!supportColor[1][to]) {
      supportColor[1][to] = true;
      supportColor[0][r[to]] = false;
      supportPairUp(r[to]);
    }
  }
}

void buildSupport( const int n ) {
  for (int i = 0; i < n; i++)
    supportColor[0][i] = (l[i] != NIL);

  for (int i = 0; i < n; i++)
    if (!supportColor[0][i])
      supportPairUp(i);
}

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

  int n, m;
  scanf("%d%d", &n, &m);
  
  memset(head, NIL, 4 * n);
  
  for (int i = 0; i < m; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    G[i].v = v - 1;
    G[i].next = head[u - 1];
    head[u - 1] = i;
  }

  printf("%d\n", 2 * n - findMatching(n));
  
  buildSupport(n);

  for (int i = 0; i < n; i++)
    printf("%d\n", (supportColor[0][i] ^ 1) + ((supportColor[1][i] ^ 1) << 1));

  return 0;
}