#include <bits/stdc++.h>

using namespace std;

const int MAX_M = 100000;
const int MAX_N = 100000;
const int NIL = -1;

struct Edge {
  int v;
  int cap;
  int next;
};

Edge G[2 * MAX_N + MAX_M];
int head[2 * MAX_N + 2];
int D[2 * MAX_N + 2];
int dad[2 * MAX_N + 2];
int pointer[2 * MAX_N + 2];
int ptr[2 * MAX_N + 2];

void addEdge(int u, int v, int cap) {
  static int ptr = 0;
  G[ptr].v = v;
  G[ptr].cap = cap;
  G[ptr].next = head[u];
  head[u] = ptr++;
}

bool BFS(int sink) {
  static int Q[2 * MAX_N + 2];
  int st = 0, fn = 1;
  Q[0] = 0;
  memset(D, 0, 4 * sink + 4);
  D[0] = 1;
  while (st != fn) {
    int u = Q[st++];
    for (int i = head[u]; i != NIL; i = G[i].next) {
      int v = G[i].v;
      if (G[i].cap && !D[v]) {
        D[v] = D[u] + 1;
        dad[v] = u;
        pointer[v] = i;
        Q[fn++] = v;
      }
    }
  }
  return D[sink];
}

int dfs(int u, int flow, int sink) {
  if (!flow || u == sink)
    return flow;
  for (; ptr[u] != NIL; ptr[u] = G[ptr[u]].next) {
    int v = G[ptr[u]].v;
    if (D[v] == D[u] + 1) {
      int newFlow = min(flow, G[ptr[u]].cap);
      int pushed = dfs(v, newFlow, sink);
      if (pushed) {
        G[ptr[u]].cap -= pushed;
        G[ptr[u] ^ 1].cap += pushed;
        return pushed;
      }
    }
  }
  return 0;
}

int maxFlow(int sink) {
  int flow = 0;
  int pushed;
  while (BFS(sink)) {
    memmove(ptr, head, 4 * sink + 4);
    do {
      pushed = dfs(0, 0x3f3f3f3f, sink);
      flow += pushed;
    } while (pushed);
  }
  return flow;
}

int main() {
  ifstream fin("felinare.in");
  ofstream fout("felinare.out");
  fin.tie(0);
  ios_base::sync_with_stdio(false);

  int n, m;

  fin >> n >> m;

  memset(head, NIL, 4 * (2 * n + 2));

  for (int i = 1; i <= n; ++ i) {
    addEdge(0, i, 1);
    addEdge(i, 0, 0);
  }

  for (int i = 0; i < m; ++ i) {
    int u, v; fin >> u >> v;
    addEdge(u, v + n, 1);
    addEdge(v + n, u, 0);
  }
  fin.close();

  for (int i = 1; i <= n; ++ i) {
    addEdge(n + i, n + n + 1, 1);
    addEdge(n + n + 1, n + i, 0);
  }

  fout << 2 * n - maxFlow(n + n + 1) << '\n';

  for (int i = 1; i <= n; ++ i) {
    int j = head[i];
    while (j != NIL && (!G[j].cap || !G[j].v)) {
      j = G[j].next;
    }
    int p = head[n + i];
    while (p != NIL && (!G[p].cap || G[p].v == 2 * n + 1)) {
      p = G[p].next;
    }
    fout << (j != NIL) + ((p != NIL) << 1) << '\n';
  }
  fout.close();

  return 0;
}