#include <bits/stdc++.h>

using namespace std;

const int NMAX = 8192;

int N, M, cup_st[NMAX], cup_dr[NMAX], sl[NMAX], sr[NMAX];
vector<int>edge[NMAX];
bool uz[NMAX];

//cup_dr e nodul cu care cuplez pe unu din stanga
void citire()
{
  ifstream fin("felinare.in");
  fin >> N >> M;
  for(int i = 0, X, Y; i < M; ++i)
  {
    fin >> X >> Y;
    edge[X - 1].push_back(Y - 1);
  }
}

void seteaza(int vertex , int pairup)
{
  cup_st[pairup] = vertex;
  cup_dr[vertex] = pairup;
  sl[vertex] = 1;
}

bool mk_cuplaj(int vertex)
{
  if(uz[vertex])
    return false;
  uz[vertex] = true;
  for(auto itr : edge[vertex])
     if(cup_st[itr] == -1)
     {
       seteaza(vertex , itr);
       return true;
     }
  for(auto itr : edge[vertex])
    if(mk_cuplaj(cup_st[itr]))
    {
      seteaza(vertex , itr);
      return true;
    }
  return false;

}

int do_cuplaj()
{
   for(int i = 0; i < N; ++i)
      cup_st[i] = cup_dr[i] = -1;
  for(bool am_cuplaj = true; am_cuplaj;)
  {
    am_cuplaj = false;
    memset(uz, 0, sizeof(uz));
    for(int i = 0; i < N; ++i) // cuplez din stanga
       if(cup_dr[i] == -1)
         am_cuplaj |= mk_cuplaj(i);
  }

  int dim = 0;
  for(int i = 0; i < N; ++i)
    dim += cup_dr[i] != -1;
  return dim;
}

void calc(int vertex)
{
  for(auto itr : edge[vertex])//acesta este un nod din dreapta
  {
    if(!sr[itr])
    {
      sr[itr] = 1;
      sl[cup_st[itr]] = 0;
      calc(cup_st[itr]);
    }
  }
}

void vertex_cover()
{
  for(int i=0; i < N; ++i)
    if(sl[i] == false)
       calc(i);
}

void solve()
{
  ofstream fout("felinare.out");
  fout << N * 2 - do_cuplaj() << '\n';
  vertex_cover();
  for(int i = 0; i < N; ++i)
  {
    if(sl[i] && sr[i])
       fout << 0 << '\n';
    else if(sl[i] && !sr[i])
        fout << 2 << '\n';
    else if(!sl[i] && sr[i]) fout << 1 << '\n';
    else fout << 3 << '\n';
  }
}

int main()
{
  citire();
  solve();
}