#include <bits/stdc++.h>

using namespace std;

struct BipartiteMatcher {
  vector<vector<int>> G;
  vector<int> L, R, vis;
  
  BipartiteMatcher(int n, int m) :
  G(n), L(n, -1), R(m, -1), vis(n) {}
  
  void AddEdge(int a, int b) {
    G[a].push_back(b);
  }
  
  bool match(int node) {
    if (vis[node])
      return false;
    vis[node] = true;
    
    for (auto vec : G[node]) {
      if (R[vec] == -1 || match(R[vec])) { // (*)
        L[node] = vec; R[vec] = node; return true;
      }
    }
    return false;
  }

  int Solve() {
    int ok = 1, n = L.size();
    while (ok--) {
      fill(vis.begin(), vis.end(), 0);
      for (int i = 0; i < n; ++i) // (**)
        if (L[i] == -1)
          ok |= match(i);
    }
    return n - count(L.begin(), L.end(), -1);
  }

  // Only include if you want vertex cover
  vector<bool> CL, CR;

  void cover(int node) {
    for (auto vec : G[node]) if (!CR[vec]) {
      CR[vec] = true; 
      CL[L[vec]] = false; 
      cover(L[vec]);
    }
  }

  int VertexCover() {
    int ret = Solve(), n = L.size();
    CL = CR = vector<bool>(n, false);
    for (int i = 0; i < n; ++i) if (R[i]) CL[i] = true;
    for (int i = 0; i < n; ++i) if (!R[i]) cover(i);
    return ret;
  }
};

int main() {
    ifstream cin("felinare.in");
    ofstream cout("felinare.out");

    int n, m; cin >> n >> m;
    BipartiteMatcher bm(n, n);
    while (m--) {
      int a, b; cin >> a >> b;
      bm.AddEdge(a - 1, b - 1);
    }

    cout << 2 * n - bm.VertexCover() << endl;
    for (int i = 0; i < n; ++i) {
      cout << 2 * (!bm.CR[i]) + (!bm.CL[i]) << '\n';
    }
    return 0;
}