#include <iostream>
#include <fstream>
#include <vector>
#define pb push_back
#define nl '\n'
using namespace std;
ifstream f ( "felinare.in" );
ofstream g ( "felinare.out" );
const int NMAX = 8192;
vector<int>G[NMAX];
int N, M, maxMatch, L[NMAX], R[NMAX];
bool viz[NMAX], sL[NMAX], sR[NMAX];
void citire()
{
    int x, y;
    f >> N >> M;

    while ( M-- )
    {
        f >> x >> y;
        G[x].pb ( y );
    }
}
bool DFS ( int x )
{
    if ( viz[x] )
        return 0;

    viz[x] = 1;

    for ( auto &y : G[x] )
    {
        if ( !L[y] || DFS ( L[y] ) )
        {
            L[y] = x;
            R[x] = y;
            //sL[x]=1;
            return 1;
        }
    }
}
void HK()
{
    bool ok = 1;
    int i;

    while ( ok )
    {
        ok = 0;

        for ( i = 1; i <= N; i++ )
            viz[i] = 0;

        for ( i = 1; i <= N; i++ )
            if ( !R[i] && DFS ( i ) )
            {
                ok = 1;
                maxMatch++;
            }
    }
}
void suport ( int x )
{
    for ( auto &y : G[x] )
    {
        if ( !sR[y] )
        {
            sR[y] = 1; ///il adaug in suport
            sL[L[y]] = 0; ///sterg din suport nodul din stanga cu care este cuplat y
            suport ( L[y] ); ///apelez recursiv pentru nodul din stanga
        }
    }
}
int main()
{
    int i, t;
    citire();
    HK();

    for ( i = 1; i <= N; i++ )
        if ( R[i] )
            sL[i] = 1;

    for ( int i = 1; i <= N; i++ )
        if ( !sL[i] )
            suport ( i );

    g << 2 * N - maxMatch << nl;

    for ( int i = 1; i <= N; i++ )
    {
        if ( sL[i] && sR[i] )
            t = 0;
        else
            if ( sR[i] )
                t = 1;
            else
                if ( sL[i] )
                    t = 2;
                else t = 3;

        g << t << nl;
    }

    f.close();
    g.close();
    return 0;
}