#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 8191;

vector<int>G[1 + MAX_N];
int l[1 + MAX_N], r[1 + MAX_N];
bool l1[1 + MAX_N], r1[1 + MAX_N];
bool viz[1 + MAX_N];
int n, m;

bool match(int nod) {
  if (viz[nod])
    return false;
  viz[nod] = 1;
  for (auto it:G[nod]) {
    if (r[it] == 0) {
      l[nod] = it;
      r[it] = nod;
      return true;
    }
  }
  for (auto it:G[nod]) {
    if (!viz[r[it]] && match(r[it])) {
      l[nod] = it;
      r[it] = nod;
      return true;
    }
  }
  return false;
}

void cuplaj() {
  bool ok;
  do {
    ok = false;
    memset(viz, 0, sizeof(viz));
    for (int i = 1; i <= n; ++i) {
      if (l[i] == 0 && match(i))
        ok = true;
    }
  } while (ok);
}

void suport(int nod) {
  for (auto it:G[nod])
    if (!r1[it]) {
      r1[it] = 1;
      l1[r[it]] = 0;
      suport(r[it]);
    }
}

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 u, v;
    scanf("%d%d", &u, &v);
    G[u].push_back(v);
  }

  cuplaj();

  int ans = 2 * n;
  for (int i = 1; i <= n; ++i)
    if (l[i])
      l1[i] = 1, ans--;
  for (int i = 1; i <= n; ++i)
    if (!l1[i])
      suport(i);

  printf("%d\n", ans);
  for (int i = 1; i <= n; ++i)
    printf("%d\n", (!l1[i]) + (!r1[i]) * 2);

  return 0;
}