#include <fstream>
#include <vector>
#include <bitset>
#define f in
#define g out

using namespace std;
ifstream in ( "felinare.in" );
ofstream out( "felinare.out" );
int n, m, i, x, y, ok, sol;
int st[8800], dr[8800], ST[8800], DR[8800];
vector<int> L[8800];
bitset<8800> viz;

int cupleaza ( int nod ){
    if ( viz[nod] )
        return 0;
    viz[nod] = 1;
    for ( auto vecin: L[nod] )
        if( !dr[vecin] ){
            dr[vecin] = nod;
            st[nod] = vecin;
            ST[nod] = 1;
            sol++;
            return 1;
        }
    for ( auto vecin: L[nod] )
        if ( cupleaza(dr[vecin]) ){
            dr[vecin] = nod;
            st[nod] = vecin;
            ST[nod] = 1;
            return 1;
        }
    return 0;
}

void dfs( int nod ){
    for ( auto vecin: L[nod] )
        if ( !DR[vecin] ){
            DR[vecin] = 1;
            ST[dr[vecin]] = 0;
            dfs(dr[vecin]);
        }
}

int main() {
    f>>n>>m;
    for ( i=1; i <= m; i++ ){
        f>>x>>y;
        L[x].push_back(y);
    }
    ok = 1;
    while (ok) {
        ok = 0;
        viz.reset();
        for ( i=1; i <= n; i++ )
            if ( !st[i] && cupleaza(i) )
                ok = 1;
    }
    g<<2*n-sol<<"\n";
    for ( i=1; i <= n; i++ )
        if ( !ST[i] )
            dfs(i);
    for ( i=1; i <= n; i++ ){
        if ( ST[i] && DR[i] ) g<<"0\n";
        if ( !ST[i] && DR[i] ) g<<"1\n";
        if ( ST[i] && !DR[i] ) g<<"2\n";
        if ( !ST[i] && !DR[i] ) g<<"3\n";
    }
    return 0;
}