#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

const int N = 2 * 8200;

vector<int> gr[N];
int st[N], dr[N], cod[N];
bool viz[N], mvc[N];

bool pairUp(int nod) {
  if (viz[nod])
    return false;
  viz[nod] = true;
  for (auto nxt: gr[nod]) {
    if (viz[nxt])
      continue;
    if (st[nxt] == 0 || pairUp(st[nxt])) {
      dr[nod] = nxt;
      st[nxt] = nod;
      return true;
    }
  }
  return false;
}

void calc(int nod) {
  for (auto nxt: gr[nod]) {
    if (mvc[nxt]) continue;
    mvc[nxt] = true;
    mvc[st[nxt]] = false;
    calc(st[nxt]);
  }
}

int main() {
  ifstream cin("felinare.in");
  ofstream cout("felinare.out");
  int n, m;
  cin >> n >> m;
  while (m--) {
    int x, y;
    cin >> x >> y;
    gr[x].push_back(y + n);
  }
  cin.close();
  bool mai_am = true;
  while (mai_am) {
    mai_am = false;
    memset(viz, 0, (n + 1) * sizeof(bool));
    for (int i = 1; i <= n; ++i)
      if (dr[i] == 0 && pairUp(i))
        mai_am = true;
  }
  int ans = 2 * n;
  for (int i = 1; i <= n; ++i)
    if (dr[i] != 0) {
      mvc[i] = true;
      --ans;
    }
  for (int i = 1; i <= n; ++i)
    if (dr[i] == 0)
      calc(i);
  for (int i = 1; i <= n; ++i)
    if (!mvc[i])
      cod[i] += 1;
  for (int i = n + 1; i <= 2 * n; ++i)
    if (!mvc[i])
      cod[i - n] += 2;
  cout << ans << "\n";
  for (int i = 1; i <= n; ++i)
    cout << cod[i] << "\n";
  cout.close();
  return 0;
}