#include <bits/stdc++.h>
#define N 8200

using namespace std;

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

vector<int> graf[N] ;
int lft[N] , rght[N] ,sol[N] ;
int n , m;
bool viz[N] , supl[N] , supr[N] ;

void citire()
{
    int i , x , y ;
    fin >> n >> m ;
    for ( i = 1 ; i <= m ; i++ )
    {
        fin >> x >> y ;
        graf[x].push_back(y) ;
    }
}

bool cuplaj(int nod)
{
    if ( viz[nod] == true )
        return false;
    viz[nod] = true ;
    for ( auto vec : graf[nod] )
    {
        if ( rght[vec] == 0 || cuplaj(rght[vec]) )
        {
            lft[nod] = vec ;
            rght[vec] = nod ;
            return true ;
        }
    }
    return false;
}

void suport(int nod)
{
    for ( auto vec : graf[nod] )
    {
        if ( supr[vec] == false )
        {
            supr[vec] = true ;
            supl[rght[vec]] = false ;
            suport(rght[vec]) ;
        }
    }
}

int main()
{
    int rez=0;
    citire() ;
    bool ok ;
    do
    {
        ok = false;
        memset(viz,false,n+1) ;
        for ( int i = 1 ; i <= n ; i++ )
            if ( lft[i] == 0 )
                ok = ok | cuplaj(i) ;
    } while(ok==true) ;
    for ( int i = 1 ; i <= n ; i++ )
        if ( lft[i] )
            supl[i] = true ;
    for ( int i = 1 ; i <= n ; i++ )
        if ( supl[i] == 0 )
            suport(i) ;
    rez=(n<<1) ;
    for ( int i = 1 ; i <= n ; i++ )
    {
        if ( supl[i] )
            rez-- ;
        if ( supr[i] )
            rez-- ;
    }
    fout << rez << '\n';
    for ( int i = 1 ; i <= n ; i++ )
    {
        sol[i] = 3;
        if ( supl[i] )
            sol[i] = sol[i] - 1 ;
        if ( supr[i] )
            sol[i] = sol[i] - 2;
        fout << sol[i] << '\n' ;
    }
}