using namespace std;

#include <cstdio>
#include <cassert>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
#include <map>

#define FIN "felinare.in"
#define FOUT "felinare.out"
#define NMAX 8192
#define PB push_back

int N, M, viz[NMAX], d[NMAX], con[NMAX], iter, Match, Cl[NMAX], Cr[NMAX];
vector <int> A[NMAX];

void read ()
{
     scanf ("%d %d\n", &N, &M);
     
     int x, y;
     for (int i = 0; i < M; ++ i)
     {
         scanf ("%d %d\n", &x, &y);
         A[x].PB (y);
     }
}

int DFS (int nod)
{
     if (viz[nod] == iter)
        return 0;
     viz[nod] = iter;

     for (vector <int> :: iterator it = A[nod].begin(); it != A[nod].end(); ++ it)
          if (d[*it] == -1)
          {
                     d[*it] = nod;
                     Cl[nod] = 1;
                     return 1;
          }     
          else
          {
              int rez = DFS (d[*it]);
              if (rez)
              {
                      d[*it] = nod;
                      Cl[nod] = 1;
                      return 1;
              }              
          }
          
     return 0;
}

void FindAlter (int nod)
{
     if (viz[nod] == iter)
        return;
     viz[nod] = iter;   
     
     Cl[nod] = 0;     
     for (vector <int> :: iterator it = A[nod].begin(); it != A[nod].end(); ++ it)
         if (d[*it] != -1)
         {
                    Cr[*it] = 1;
                    FindAlter (d[*it]);
         }    
     
}

void solve ()
{
     for (int i = 1; i <= N; ++ i)
         d[i] = -1;
         
     int verif = 1;
     while (verif)
     {
           verif = 0;
           for (int i = 1; i <= N; ++ i)
               if (!con[i])
               {
                          ++ iter;
                          DFS (i);
                          verif = con[i] = 1;
               }
     }             
     
     for (int i = 1; i <= N; ++ i)
         if (d[i] != -1)
         {
                  //fprintf (stderr, "%d %d\n", d[i], i);
                  ++ Match;
         }
         
     for (int i = 1; i <= N; ++ i)
         if (!Cl[i])
         {
                         ++ iter;
                         FindAlter (i);     
         } 
         
     printf ("%d\n", 2*N - Match);    
         
     for (int i = 1; i <= N; ++ i)
         printf ("%d\n", 1 - Cl[i] + 2 * (1 - Cr[i]));         
     
}

int
 main ()
{
     freopen (FIN, "rt", stdin);
     freopen (FOUT, "wt", stdout);
     
     read ();
     solve ();
      
     return 0;
}