#include<fstream>
#include<bitset>
#include<vector>
#include<queue>
#include<set>
using namespace std ;

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

#define maxn 18191
#define NN 8191
#define RR 10000

int N, E ;

bitset<maxn> sel ;
vector<int> graf[maxn] ;
int st[maxn], cuplaj[maxn] ;

queue<int> coada ;

bool stanga[NN], dreapta[NN] ;

set<int> T ;
vector<int> acop ;

int solutie[NN] ;

void citire()
{
    fin >> N >> E ;
    for(int i = 0; i < E; ++i )
    {
        int x, y ;
        fin >> x >> y ;
        int ny = y + RR ;
        graf[x].push_back(ny);
    }
}

bool dfs(int nod)
{
    if( sel[nod] )
        return false ;

    sel[nod] = true ;

    for(size_t i = 0; i < graf[nod].size(); ++i )
    {
        int vecin = graf[nod][i] ;
        int de_unde = st[vecin] ;

        if( de_unde == false || dfs( de_unde ) == true )
        {
            st[vecin] = nod ;
            cuplaj[nod] = vecin ;
            return true ;
        }
    }

    return false ;
}

void multimea_T()
{
    while( coada.empty() == false )
    {
        int nod = coada.front() ;
        sel[nod] = true ;

        if( nod > RR && sel[ st[nod] ] == false )
        {
            coada.push( st[nod] ) ;
            T.insert( st[nod] ) ;
            continue ;
        }

        for(size_t i = 0; i < graf[nod].size(); ++i )
        {
            int vecin = graf[nod][i] ;

            if( sel[vecin] == false && nod < RR && cuplaj[nod] != vecin )
            {
                coada.push(vecin) ;
                acop.push_back( vecin ) ;
            }
        }

        coada.pop() ;
    }
}

int main()
{
    citire() ;

    int nr = 0 ;
    bool ok ;

    do
    {
        ok = false;

        for(int i = 1; i <= N; ++i )
        {
            if( cuplaj[i] == 0 && dfs(i) == true )
            {
                ++nr ;
                ok = true ;
            }
        }

        sel.reset() ;

    } while( ok == true ) ;

    sel.reset() ;

    for(int i = 1; i <= N; ++i )
        if( cuplaj[i] == 0 )
            coada.push(i), sel[i] = true, T.insert(i) ;

    multimea_T() ;

    //for(set<int>::iterator it = T.begin(); it != T.end(); ++it )
        //fout << *it << " " ;

    for(int i = 1; i <= N; ++i )
        if( T.find( i ) == T.end() )
            acop.push_back(i) ;

    int nrs = 2 * N - nr ;

    fout << nrs << "\n" ;

    for(size_t i = 0; i < acop.size(); ++i )
    {
        if( acop[i] < RR )
            stanga[ acop[i] ] = true ;
        else
            dreapta[ acop[i] - RR ] = true ;
    }

    for(int i = 1; i <= N; ++i )
    {
        if( stanga[i] == false && dreapta[i] == false )
            fout << "3" << "\n" ;
        if( stanga[i] == true && dreapta[i] == false )
            fout << "2" << "\n" ;
        if( stanga[i] == false && dreapta[i] == true )
            fout << "1" << "\n" ;
        if( stanga[i] == true && dreapta[i] == true )
            fout << "0" << "\n" ;
    }

    return 0 ;
}