#include <bits/stdc++.h>
#define pb push_back
#define x first
#define y second
using namespace std;
const int N = 100005 ;
ifstream in ("felinare.in");
ofstream out ("felinare.out");
vector < int > v [ N ] ;
pair < int , int > g [ N ] ;
int n , m , st [ N ] , dr [ N ] , change , cnt ;
bool viz [ N ] ;
vector < bool > stare_st ( N , 0 ) , stare_dr ( N , 1 ) ;
bool cupla ( int &nod )  {
    if ( viz [ nod ] )  return 0 ;
    viz [ nod ] = 1 ;
    vector < int > :: iterator it ;
    for ( it = v [ nod ].begin() ; it != v [ nod ].end() ; ++ it )  {
        if ( !dr [ *it ] )  {
            dr [ *it ] = nod ;
            st [ nod ] = *it ;
            return 1 ;
        }
    }
      for ( it = v [ nod ].begin() ; it != v [ nod ].end() ; ++ it )  {
        if ( cupla ( dr [ *it ] ) )  {
            dr [ *it ] = nod ;
            st [ nod ] = *it ;
            return 1 ;
        }
    }
    return 0 ;
}

void dfs ( int nod )    {
    if ( stare_st [ nod ] == 1 )    return ;
    stare_st [ nod ] = 1 ;
    vector < int > :: iterator it;
    for ( it = v [ nod ].begin() ; it != v [ nod ].end() ; ++ it )  {
        if ( *it != st [ nod ] && stare_dr [ *it ] == 1 )    {
            stare_dr [ *it ] = 0 ;
            dfs( dr [ *it ] ) ;
        }
    }
}

int main()  {
    int x , y , i ;
    in >> n >> m ;
    for ( i = 1 ; i <= m ; ++ i )  {
        in >> x >> y ;
        v [ x ].pb ( y ) ;
    }
    change = 1 ;
    while ( change )    {
        change = 0 ;
        for ( i = 1 ; i <= n ; ++ i )       viz [ i ] = 0 ;
        for ( i = 1 ; i <= n ; ++ i )
            if ( !st [ i ] )    change |= cupla ( i ) ;
    }
    for ( i = 1 ; i <= n ; ++ i )   {
        if ( st [ i ] ) cnt ++ ;
        else            dfs ( i ) ;
    }
    out << 2*n - cnt << '\n' ;

    for ( i = 1 ; i <= n ; ++ i )   {
    if ( !stare_st [ i ] && !stare_dr [ i ] ) out << "0\n" ;
    if ( stare_st [ i ] && !stare_dr [ i ] ) out << "1\n" ;
    if ( !stare_st [ i ] && stare_dr [ i ] ) out << "2\n" ;
    if ( stare_st [ i ] && stare_dr [ i ] ) out << "3\n" ;
    }



}