#include <fstream>
#include <cstring>
#include <vector>
using namespace std;

ifstream F("felinare.in");
ofstream G("felinare.out");

const int Nmax = 8500;

vector<int> V[Nmax];
int N,M;

int paired[Nmax];
int left_pair[Nmax];
int right_pair[Nmax];

int left_mvc[Nmax];
int right_mvc[Nmax];

int pair_up(int lnode)
{
    if ( lnode == 0 )
        return 1;
    paired[lnode] = 1;
    for (size_t i=0;i<V[lnode].size();++i)
    {
        int rnode = V[lnode][i];
        int up_node = left_pair[rnode];
        if ( paired[ up_node ] == 0 )
            if ( pair_up( up_node ) == 1 )
            {
                right_pair[ lnode ] = rnode;
                left_pair[ rnode ] = lnode;
                return 1;
            }
    }
    return 0;
}

void cover_up(int lnode)
{
    if ( lnode == 0 )
    {
        return;
    }
    for (size_t j=0;j<V[lnode].size();++j)
    {
        int rnode = V[lnode][j];
        if ( right_mvc[ rnode ] == 0 )
            if ( left_pair[ rnode ] != 0 && right_pair[ rnode ] != lnode )
            {
                left_mvc[ left_pair[rnode] ] = 0;
                right_mvc[ rnode ] = 1;
                cover_up( left_pair[rnode] );
            }
    }
}

int main()
{
    F>>N>>M;
    for (int i=1,x,y;i<=M;++i)
    {
        F>>x>>y;
        V[ x ].push_back( y );
    }

    int better = 1, size = 0;
    while ( better )
    {
        better = 0;
        memset(paired,0,sizeof(paired));
        for (int i=1;i<=N;++i)
            if ( right_pair[i] == 0 )
                if ( pair_up( i ) == 1 )
                    better = 1 , ++size;
    }

    for (int i=1;i<=N;++i)
        if ( right_pair[i] != 0 )
            left_mvc[i] = 1;
    for (int i=1;i<=N;++i)
        if ( left_mvc[i] == 0 )
            cover_up( i );

    G<<N*2-size<<'\n';
    for (int i=1;i<=N;++i)
    {
        int fs = 0 , sc = 0;
        if ( left_mvc[ i ] == 0 ) fs = 1;
        if ( right_mvc[ i ] == 0 ) sc = 1;
        if ( fs == 0 && sc == 0 ) G<<"0\n";
        if ( fs == 1 && sc == 0 ) G<<"1\n";
        if ( fs == 0 && sc == 1 ) G<<"2\n";
        if ( fs == 1 && sc == 1 ) G<<"3\n";
    }
}