#include <bits/stdc++.h>

using namespace std;
const int VMAX = 8191;
const int EMAX = 2e4;
const int NONE = -1;
const int LEFT = 0, RIGHT = 1;

int from[1 + 2 * VMAX]; int to[1 + VMAX];
bool used[1 + 2 * VMAX]; vector<int> g[1 + VMAX];
bool getPath (int root) {
   if (used[root])
     return false;
   used[root] = true;
   for (int node : g[root]) {
      if (from[node] == NONE || getPath (from[node])) {
        to[root] = node;
        from[node] = root;
        return true;
      }
   }
   return false;
}

int V, E;
int MaxMatching () {
   int match = 0; bool found;
   do {
     found = false;
     for (int node = 1; node <= V; node ++)
        if (to[node] == NONE && getPath (node)) {
          found = true;
          match ++;
        }
     for (int node = 1; node <= V; node ++)
        used[node] = false;
   } while (found);

   return match;
}

/// MIS = V / MVC; size (MVC) = size(MaxMatching)
/// MVC = !vis(L) + vis(R)

bool visited[1 + 2 * VMAX];
void dfs (int root, int side) {
    visited[root] = true;
    if (side == RIGHT)
      dfs (from[root], LEFT);
    else { /// left
      for (int node : g[root])
         if (node != to[root])
           dfs (node, RIGHT);
    }
}

bool in_MVC[1 + 2 * VMAX];
bool in_MIS[1 + 2 * VMAX];

int main()
{
   ifstream in ("felinare.in");
   in >> V >> E;
   for (int i = 1; i <= E; i ++) {
      int a, b; in >> a >> b;
      g[a].push_back (b + V);
   }
   for (int node = 1; node <= V; node ++)
      to[node] = NONE;
   for (int node = V + 1; node <= 2 * V; node ++)
      from[node] = NONE;

   ofstream out ("felinare.out");
   out << 2 * V - MaxMatching () << "\n";

   for (int node = 1; node <= 2 * V; node ++)
      visited[node] = false;
   for (int node = 1; node <= V; node ++)
      if (to[node] == NONE && !visited[node])
        dfs (node, LEFT);

   for (int node = 1; node <= V; node ++)
      if (!visited[node])
        in_MVC[node] = true;
   for (int node = V + 1; node <= 2 * V; node ++)
      if (visited[node])
        in_MVC[node] = true;

   for (int node = 1; node <= 2 * V; node ++)
      in_MIS[node] = !in_MVC[node];
   for (int node = 1; node <= V; node ++) {
      if (!in_MIS[node] && !in_MIS[node + V])
        out << 0;
      else if (in_MIS[node] && !in_MIS[node + V])
        out << 1;
      else if (!in_MIS[node] && in_MIS[node + V])
        out << 2;
      else
        out << 3;
      out << "\n";
   }
    return 0;
}