#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

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

const int N = 8192;

int n,m,L[N],R[N],SOL;
vector<int> G[N];
bool USE[N];

void READ ()
{

    in>>n>>m;

    for( int x,y ; m ; --m )
    {

        in>>x>>y;

        G[x].push_back(y);

    }

}

bool PAIRUP (int nod)
{

    if( USE[nod] )
        return 0;

    USE[nod]=1;

    for( vector<int>::iterator it=G[nod].begin() ; it < G[nod].end() ; ++it )
        if( !R[*it] )
        {

            R[*it]=nod;
            L[nod]=*it;

            ++SOL;

            return 1;

        }

    for( vector<int>::iterator it=G[nod].begin() ; it < G[nod].end() ; ++it )
        if( PAIRUP(R[*it]) )
        {

            R[*it]=nod;
            L[nod]=*it;

            return 1;

        }

   return 0;

}

void SOLVE ()
{

    for( bool ok=1 ; ok ; )
    {

        ok=0;

        memset(USE,0,sizeof(USE));

        for( int i=1 ; i <= n ; ++i )
        {

            if( L[i] )
                continue;

            if( PAIRUP(i) )
                ok=1;

        }

    }

}

void PRINT ()
{

    out<<2*n-SOL<<'\n';

    for( int i=1 ; i <= n ; ++i )
    {

        if( L[i] && R[i] )
        {
            out<<"0\n";
            continue;
        }

        if( R[i] )
        {
            out<<"1\n";
            continue;
        }

        if( L[i] )
        {
            out<<"2\n";
            continue;
        }

        out<<"3\n";

    }

}

int main ()
{

    READ ();
    SOLVE ();
    PRINT ();

    return 0;

}