#include <fstream>
#include <vector>
#include <bitset>

using namespace std;

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

const int max_size = 8192;

short st[max_size], dr[max_size], l[max_size], r[max_size];
vector <short> mc[max_size];
bitset <max_size> viz;

bool pairup (int nod)
{
   if (viz[nod])
   {
      return false;
   }
   viz[nod] = 1;
   for (auto f : mc[nod])
   {
      if (!dr[f])
      {
         st[nod] = f;
         dr[f] = nod;
         return true;
      }
   }
   for (auto f : mc[nod])
   {
      if (pairup(dr[f]))
      {
         st[nod] = f;
         dr[f] = nod;
         return true;
      }
   }
   return false;
}

void dfs (int nod)
{
   l[nod] = 1;
   viz[nod] = 1;
   for (auto f : mc[nod])
   {
      if (!viz[dr[f]] && dr[f] > 0 && dr[f] != nod)
      {
         r[f] = 1;
         dfs(r[f]);
      }
   }
}

int main ()
{
   int n, q;
   in >> n >> q;
   while (q--)
   {
      int x, y;
      in >> x >> y;
      mc[x].push_back(y);
   }
   /// faci cuplaj ca dupa vine min vertex cover
   while (1)
   {
      for (int i = 1; i <= n; i++)
      {
         viz[i] = 0;
      }
      bool ok = false;
      for (int i = 1; i <= n; i++)
      {
         if (!st[i])
         {
            ok |= pairup(i);
         }
      }
      if (!ok)
      {
         break;
      }
   }
   /// bagi mvxcover, nodurile care nu ies in mvx => noduri aprinse
   /// orcm teoretic pot afisa deja nr de felinare ca e 2 * n - cuplaj
   for (int i = 1; i <= n; i++)
   {
      viz[i] = 0;
   }
   for (int i = 1; i <= n; i++)
   {
      if (!st[i])
      {
         dfs(i);
      }
   }
   /// si acum fac invers, nu iau nodurile din mvxc
   int rez = 0;
   for (int i = 1; i <= n; i++)
   {
      if (st[i] > 0)
      {
         rez++;
      }
   }
   out << 2 * n - rez << '\n';
   for (int i = 1; i <= n; i++)
   {
      int ct = 0;
      if (l[i])
      {
         ct++;
      }
      if (!r[i])
      {
         ct += 2;
      }
      out << ct << '\n';
   }
   in.close();
   out.close();
   return 0;
}