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

using namespace std;

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

const int max_size = 8192;

int st[2 * max_size + 5], dr[2 * max_size + 5];
vector <int> mc[2 * max_size + 5];
bitset <2 * max_size + 5> viz, cpl;

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)
{
   //cout << nod << " ";
   for (auto f : mc[nod])
   {
      //cout << "*";
      if (!cpl[f])
      {
         cpl[dr[f]] = 0;
         cpl[f] = 1;
         dfs(dr[f]);
      }
   }
}

int main ()
{
   int n, q;
   in >> n >> q;
   while (q--)
   {
      int x, y;
      in >> x >> y;
      mc[x].push_back(y + n);
   }
   /// faci cuplaj ca dupa vine min vertex cover
   while (1)
   {
      for (int i = 1; i <= 2 * 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 <= 2 * 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++;
         cpl[i] = 1;
      }
   }
   out << 2 * n - rez << '\n';
   for (int i = 1; i <= n; i++)
   {
      /// n a picat SIUUUUUUU
      if (cpl[i] && cpl[i + n])
      {
         out << 0 << '\n';
      }
      if (!cpl[i] && cpl[i + n])
      {
         out << 1 << '\n';
      }
      if (cpl[i] && !cpl[i + n])
      {
         out << 2 << '\n';
      }
      if (!cpl[i] && !cpl[i + n])
      {
         out << 3 << '\n';
      }
   }
   in.close();
   out.close();
   return 0;
}