#include <iostream>
#include <string.h>
#include <cstdio>
#include <vector>

using namespace std;

vector<vector<int> > G, GR;

int  L[10000],  R[10000], viz[10000];
int CL[10000], CR[10000];

int pair_up(int nod) {
  if (viz[nod]) return 0;
  viz[nod] = 1;

  for (int i = 0; i < G[nod].size(); ++i) {
    int nod2 = G[nod][i];
    if (!R[nod2] || pair_up(R[nod2])) {
      L[nod] = nod2; R[nod2] = nod;
      return 1;
    }
  }
  return 0;
}
void markR(int nod, int m);
void markL(int nod, int m);


void cover(int nod) {
  for (int i = 0; i < G[nod].size(); ++i) {
    int nod2 = G[nod][i];
    if (!CR[nod2]) {
      CR[nod2] = 1;
      CL[L[nod2]] = 0;
      cover(L[nod2]);
    }
  }
}

int main() {
  freopen("felinare.in", "r", stdin);
  freopen("felinare.out", "w", stdout);
  int N, M;
  scanf("%d %d", &N, &M);
  G.resize(N + 7);
  GR.resize(N + 7);
  while (M--) {
    int a, b;  // a->b.
    scanf("%d %d", &a, &b);
    G[a].push_back(b);
    GR[b].push_back(a);
  }

  // Cuplaj.
  bool ok = true;
  while (ok) {
    ok = false;
    memset(viz, 0, sizeof(viz));
    for (int i = 1; i <= N; ++i) if (!L[i]) ok |= pair_up(i);
  }

  int aprinse = 2 * N;
  for (int i = 1; i <= N; ++i) if (L[i]) --aprinse;

  printf("%d\n", aprinse);

  // Cover.
  for (int i = 1; i <= N; ++i) if (!L[i] && !CL[i] && G[i].size()) {
    CL[i] = 1;
    for (int j = 0; j < G[i].size(); ++j) {
      int nod2 = G[i][j];
      if (R[nod2]) markR(nod2, 1);
    }
  }
  for (int i = 1; i <= N; ++i) if (L[i]) CL[i] = 1;
  for (int i = 1; i <= N; ++i) if (!L[i]) cover(i);
  for (int i = 1; i <= N; ++i) {
    int f = 3;
    if (CL[i] == 1) f -= 1;
    if (CR[i] == 1) f -= 2;
    printf("%d\n", f);
  }
  return 0;
}