#include<fstream>
#include<bitset>
#include<vector>
#include<queue>
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] ;
 
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() ;
        coada.pop() ;
        sel[nod] = true ;
 
        if( nod > RR && sel[ st[nod] ] == false )
        {
            coada.push( st[nod] );
            sel[st[nod] ] = true ;
            continue ;
        }
        if( nod  > RR)
            continue;
 
        for(size_t i = 0; i < graf[nod].size(); ++i )
        {
            int vecin = graf[nod][i] ;
 
            if( sel[vecin] == false && cuplaj[nod] != vecin )
            {
                coada.push(vecin) ;
                sel[vecin] = true ;
                acop.push_back( vecin ) ;
            }
        }
    }
}
 
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 ;
 
    multimea_T() ;
 
    //for(set<int>::iterator it = T.begin(); it != T.end(); ++it )
        //fout << *it << " " ;
 
    for(int i = 1; i <= N; ++i )
        if( sel[i] == false )
            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 ;
}