#include <fstream>
#include <cstring>
#include <vector>
using namespace std;

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

const int Nmax = 8200;

int L[Nmax],R[Nmax],Fixed[Nmax];
vector<int> A[Nmax];

int St[Nmax],Dr[Nmax];

int N,M,Size;

#define IT(type) vector<type>::iterator

int LookUp(int Nod)
{
    if ( Fixed[Nod] == 1 ) return 0;
    Fixed[Nod] = 1;

    for (IT(int) it=A[Nod].begin();it!=A[Nod].end();++it)
        if ( R[ *it ] == 0 )
        {
            L[ Nod ] = *it;
            R[ *it ] = Nod;
            return 1;
        }
    for (IT(int) it=A[Nod].begin();it!=A[Nod].end();++it)
        if ( LookUp( R[ *it ] ) == 1 )
        {
            L[ Nod ] = *it;
            R[ *it ] = Nod;
            return 1;
        }
    return 0;
}

void Cover(int Nod)
{
    for (IT(int) it=A[Nod].begin();it!=A[Nod].end();++it)
        if ( Dr[ *it ] == 0 ) // daca nodul din dreapta nu e acoperit
        {
            Dr[ *it ] = 1; // acopar nodul din dreapta
            St[ R[*it] ] = 0; // demarchez perechea nodului din dreapta
            Cover( R[ *it ] ); // validez acoperirea perechii nodului drept
        }
}

int main()
{
    F>>N>>M;
    for (int i=1,a,b;i<=M;++i)
    {
        F>>a>>b;
        A[ a ].push_back( b );
    }

    for (int Ok=1; Ok == 1; )
    {
        Ok = 0;
        memset(Fixed,0,sizeof(Fixed));
        for ( int i=1;i<=N;++i )
            if ( L[i] == 0 )
                Ok |= LookUp( i );
    }

    // Incep de la un cuplaj valid si pornescu cu nodurile din stanga

    for (int i=1;i<=N;++i)
        if ( L[i] )
        {
            St[i] = 1;
            Size ++;
        }

    // trebuie sa validez ocnfiguratiile pentru totate nodurile din stanga cu
    // configuratii nevalidate

    for (int i=1;i<=N;++i)
        if ( L[i] == 0 )
            Cover( i );

    G<<N*2-Size<<'\n';
    for( int i=1;i<=N;++i)
    {
        if ( St[i] == 1 && Dr[i] == 1 ) G<<"0\n";
        if ( St[i] == 0 && Dr[i] == 1 ) G<<"1\n";
        if ( St[i] == 1 && Dr[i] == 0 ) G<<"2\n";
        if ( St[i] == 0 && Dr[i] == 0 ) G<<"3\n";
    }

    F.close();
    G.close();
    return 0;
}