#include <bits/stdc++.h>

using namespace std;

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

/// "TEORIE":
/// vertex cover = o multime de NODURI ale unui graf astfel incat pentru orice muchie (u, v) ORI u ORI v se afla in multime
/// minimum vertex cover = un vertex cover de CARDINALITATE MINIMA
/// independent set = o multime de NODURI ale unui graf astfel incat oricare 2 noduri din multime nu sunt adiacente(adica nu sunt unite de vreo muchie)
/// maximum independet set = un independent set de CARDINALITATE MAXIMA

/// INTRU-UN GRAF BIPARTIT:
/// minimum vertex cover = cuplaj maxim
/// maximum independent set = N - minimum vertex cover = N - cuplaj maxim; N = numarul de noduri ale grafului
/// daca consider in fiecare nod felinarul ce lumineaza strazile ce ies din el ca fiind de tipul 1
/// si cel ce lumineaza strazile ce intra in el ca fiind de tipul 2 si creez un nou GRAF BIPARTIT
/// ce are 2 * N noduri(N felinare de tipul 1 si N felinare de tipul 2) conditia pentru ca o strada
/// sa nu fie luminata complet este ca pentru o muchie (u, v)(u din "stanga" si v din "dreapta") sa nu am si u si v aprinse
/// adica oricare 2 noduri adiacente "stinse"
/// astfel pot aprinde doar noduri neadiacente, adica un INDEPENDENT SET
/// cum se cere sa fie cat mai multe felinare aprinse, trebuie construit un MAXIMUM INDEPENDENT SET

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;
}