#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
using namespace std;

#define nmax 8200


int L[nmax], R[nmax], SL[nmax], SR[nmax], C;
vector<int> G[nmax];
int N, M, used[nmax], X, Y;

int PairUp(int node)
{
    if(used[node]) return 0;
    used[node] = 1;
    vector<int> :: iterator it;
    for(it = G[node].begin(); it != G[node].end(); ++ it)
    {
           if(!R[*it])
           {
                      L[node] = *it;
                      R[*it] = node;
                      return 1;
           }
    }
    for(it = G[node].begin(); it != G[node].end(); ++ it)
    {
           if(PairUp(R[*it]))
           {
                             L[node] = *it;
                             R[*it] = node;
                             return 1;
           }
    }
    return 0;
}

void Cuplaj()
{
     for(int ok = 1; ok; )
     {
             ok = 0;
             memset(used, 0, sizeof(used));
             for(int i = 1; i <= N; i++)
                     if(!L[i] && PairUp(i))
                              ok = 1;
     }
}

void minVertexCover(int node)
{
     vector<int> :: iterator it;
     for(it = G[node].begin(); it != G[node].end(); ++ it)
     {
            if(!SR[*it])
            {
                     SR[*it] = 1;
                     SL[ R[*it] ] = 0;
                     minVertexCover(R[*it]);
            }
     }
}

int main()
{
    freopen("felinare.in", "r", stdin);
    freopen("felinare.out", "w", stdout);
    int i;
    scanf("%i %i", &N, &M);
    for(i = 1; i <= M; i++)
    {
          scanf("%i %i", &X, &Y);
          G[X].push_back(Y);
    }  
    Cuplaj();
    for(i = 1; i <= N; i++)
          if(L[i])
                  C ++;
    printf("%i\n", (N << 1) - C);
    for(i = 1; i <= N; i++)
          if(L[i])
                  SL[i] = 1;
    for(i = 1; i <= N; i++)
          if(!L[i])
                   minVertexCover(i);
    for(i = 1; i <= N; i++) 
    {
          if(SL[i] && SR[i]) printf ("%i\n", 0);
          if(!SL[i] && SR[i]) printf ("%i\n", 1);
          if(SL[i] && !SR[i]) printf ("%i\n", 2);
          if(!SL[i] && !SR[i]) printf ("%i\n", 3);
    }
    return 0;
}