#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 markR(int nod, int m) {
  if (CR[nod]) return;
  printf("R: %d %d\n", nod, m);
  CR[nod] = m + 1;
  for (int i = 0; i < GR[nod].size(); ++i) {
    int nod2 = GR[nod][i];
    markL(nod2, m ^ 1);
  }
}
void markL(int nod, int m) {
  if (CL[nod]) return;
  printf("L: %d %d\n", nod, m);
  CL[nod] = m + 1;
  for (int i = 0; i < G[nod].size(); ++i) {
    int nod2 = G[nod][i];
    markR(nod2, m ^ 1);
  }
}
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.
  ok = false;
  for (int i = 1; i <= N; ++i) if (!L[i] && !CL[i] && G[i].size()) {
    ok = true;
    markL(i, 0);
  }
  if (!ok) for (int i = 1; i <= N; ++i) if (L[i]) CL[i] = 2;
  for (int i = 1; i <= N; ++i) {
    int f = 3;
    if (CL[i] == 2) f -= 1;
    if (CR[i] == 2) f -= 2;
    printf("%d\n", f);
  }
  return 0;
}