#include <bits/stdc++.h>

using namespace std;

struct Graph {
  int n;
  vector<bool> vis;
  vector<int> match;
  vector<vector<int>> adj;
  Graph(int n_) : n(n_), vis(n), match(n, -1), adj(n) {}
  void AddEdge(int u, int v) {
    adj[u].emplace_back(v);
  }
  int GetMaxMatching() {
    int done = false, max_matching = 0;
    while (!done) {
      done = true;
      fill(vis.begin(), vis.end(), false);
      for (int i = 0; i < n / 2; ++i) {
        if (match[i] == -1 && CanMatch(i)) {
          done = false;
          ++max_matching;
        }
      }
    }
    return max_matching;
  }
  bool CanMatch(int node) {
    if (vis[node]) return false;
    vis[node] = true;
    auto SetNode = [&](int x) {
      match[node] = x;
      match[x] = node;
      return true;
    };
    for (int &x : adj[node]) {
      if (match[x] == -1) {
        return SetNode(x);
      }
    }
    for (int &x : adj[node]) {
      if (CanMatch(match[x])) {
        return SetNode(x);
      }
    }
    return false;
  }
  void DFS(int node) {
    vis[node] = true;
    for (int &x : adj[node]) if (!vis[x]) {
      assert(match[x] != -1); // daca nu ar avea pereche, cuplajul nu ar fi maxim
      vis[x] = true;
      DFS(match[x]);
    }
  }
  vector<int> Solve() {
    fill(vis.begin(), vis.end(), false);
    for (int i = 0; i < n / 2; ++i) {
      if (match[i] == -1) {
        DFS(i);
      }
    }
    vector<int> ans(n / 2);
    for (int i = 0; i < n / 2; ++i) {
      if (vis[i]) ans[i] |= 1;
      if (!vis[i + n / 2]) ans[i] |= 2; 
    }
    return ans;
  }  
};

int main() {
  ifstream cin("felinare.in");
  ofstream cout("felinare.out");
  
  int n, m; cin >> n >> m;
  Graph g(2 * n);
  for (int i = 0; i < m; ++i) {
    int a, b; cin >> a >> b;
    g.AddEdge(a - 1, b + n - 1);
  }
  // fiecare nod -> 2 noduri
  // nod intrare + nod iesire
  // in stanga avem nodurile de iesire
  // in dreapta nodurile de intrare
  // pt o muchie din graful initial a -> b
  // ducem muchie iesire_a -> intrare_b
  // pt ca muchiile sa nu fie 'sigure' trebuie sa
  // activam noduri a.i. sa nu avem 2 noduri adiacente activate
  // -> cautam maximum independent set pe bipartit -> ez
 
  int answer = 2 * n - g.GetMaxMatching();
  cout << answer << endl;
  auto ans = g.Solve();
  for (int &x : ans) {
    cout << x << '\n';
  }
}