/*
 * Code by Spiromanul
 */


#include <fstream>
#include <vector>
#include <bitset>

#define pb push_back

const char IN [ ] = "felinare.in" ;
const char OUT [ ] = "felinare.out" ;
const int MAX = 8999 ;

using namespace std;

ifstream fin ( IN ) ;
ofstream fout ( OUT ) ;

vector < int > gr [ MAX ] ;
bitset < MAX > viz ;
bitset < MAX > felinar1 ;
bitset < MAX > felinar2 ;

int n , m ;

int leftboss [ MAX ] , rightboss [ MAX ] ;

inline int cuplaj ( int nod )
{
    if ( viz [ nod ] )
        return 0 ;
    viz [ nod ] = 1 ;
    for ( auto x : gr [ nod ] )
        if ( rightboss [ x ] == 0 )
        {
            rightboss [ x ] = nod ;
            leftboss [ nod ] = x ;
            return 1 ;
        }
    for ( auto x : gr [ nod ] )
        if ( cuplaj ( rightboss [ x ] ) )
        {
            rightboss [ x ] = nod ;
            leftboss [ nod ] = x ;
            return 1 ;
        }
    return 0 ;
}

inline void set_independent_maximal ( int nod )
{
    if ( felinar1 [ nod ] )
        return ;
    felinar1 [ nod ] = 1 ;
    for ( auto x : gr [ nod ] )
        if ( x != leftboss [ nod ] )
        {
            felinar2 [ x ] = 1 ;
            set_independent_maximal( rightboss [ x ] ) ;
        }
}

int main(           )
{
    fin >> n >> m ;
    for ( int i = 1 ; i <= m ; ++ i )
    {
        int x , y ;
        fin >> x >> y ;
        gr [ x ].pb ( y ) ;
    }
    ///////////////
    int cuplate = 0 ;
    int ok = 0 ;
    do {
        ok = 0 ;
        viz.reset ( ) ;
        for ( int i = 1 ; i <= n ; ++ i )
            if ( leftboss [ i ] == 0 )
            {
                if ( cuplaj ( i ) )
                {
                    ok = 1 ;
                    ++ cuplate ;
                }
            }
    }while ( ok );
    //////////////
    for ( int i = 1 ; i <= n ; ++ i )
        if ( not leftboss [ i ] )
            set_independent_maximal( i ) ;
    //////////////////
    for ( int i = 1 ; i <= n ; ++ i )
        felinar2 [ i ] = 1 - felinar2 [ i ] ;
    /////////////
    fout << ( n << 1 ) - cuplate  << '\n' ;
    for ( int i = 1 ; i <= n ; ++ i )
    {
        if ( felinar1 [ i ] + felinar2 [ i ] == 0 )
            fout << 0 << '\n' ;
        else if ( felinar1 [ i ] > 0 and felinar2 [ i ] == 0 )
            fout << 1 << '\n' ;
        else if ( felinar2 [ i ] > 0 and felinar1 [ i ] == 0 )
            fout << 2 << '\n' ;
        else if ( felinar1 [ i ] > 0 and felinar2 [ i ] > 0 )
            fout << 3 << '\n' ;
    }
    return 0;
}