#include <bits/stdc++.h>

using namespace std;

ifstream fin("felinare.in");
ofstream fout("felinare.out");

const int MAXN = 1 << 13;
vector<int> G[MAXN];
int n, m, l[MAXN], r[MAXN], in_cover[MAXN << 1];
bitset<MAXN> viz;

bool dfs(int u) {
  if (viz[u])
    return false;
  viz[u] = true;
  for (int v : G[u])
    if (!r[v]) {
      l[u] = v;
      r[v] = u;
      return true;
    }
  for (int v : G[u])
    if (dfs(r[v])) {
      l[u] = v;
      r[v] = u;
      return true;
    }
  return false;
}

void vertex_cover(int u) {
  if (viz[u])
    return;
  viz[u] = true;
  for (int v : G[u])
    if (!in_cover[v + n]) {
      in_cover[r[v]] = false;
      in_cover[v + n] = true;
      vertex_cover(r[v]);
    }
}

int main() {
  fin >> n >> m;
  for (int i = 0; i < m; ++i) {
    int u, v; fin >> u >> v;
    G[u].emplace_back(v);
  }
  for (bool change = true; change; ) {
    change = false;
    viz.reset();
    for (int u = 1; u <= n; ++u)
      if (!l[u])
        change |= dfs(u);
  }
  int cuplaj = 0;
  for (int u = 1; u <= n; ++u)
    cuplaj += in_cover[u] = (l[u] > 0);
  fout << (n << 1) - cuplaj << '\n';
  viz.reset();
  for (int u = 1; u <= n; ++u)
    if (!in_cover[u])
      vertex_cover(u);
  for (int u = 1; u <= n; ++u)
    fout << ((!in_cover[u]) | ((!in_cover[u + n]) << 1)) << '\n';
  fin.close();
  fout.close();
  return 0;
}