#include<fstream>
#include<cstring>
#include<vector>
#define DIM 8195
using namespace std;
ifstream fin("felinare.in");
ofstream fout("felinare.out");
int LeftMatch[DIM], RightMatch[DIM], ok, LeftSuport[DIM], RightSuport[DIM], MatchSize;
int f[DIM], n, m;
vector<int> v[DIM];
int Match( int nod ){
    if( f[nod] == 1 )
        return 0;
    f[nod] = 1;
    for( int i = 0; i < v[nod].size(); i++ ){
        if( RightMatch[ v[nod][i] ] == 0 ){
            MatchSize++;
            LeftMatch[nod] = v[nod][i];
            RightMatch[ v[nod][i] ] = nod;
            return 1;
        }
    }
    for( int i = 0; i < v[nod].size(); i++ ){
        if( Match( v[nod][i] ) == 1 ){
            LeftMatch[nod] = v[nod][i];
            RightMatch[ v[nod][i] ] = nod;
            return 1;
        }
    }
    return 0;
}
void Suport( int nod ){
    for( int i = 0; i < v[nod].size(); i++ ){
        if( RightSuport[ v[nod][i] ] == 0 ){
            RightSuport[ v[nod][i] ] = 1;
            LeftSuport[ RightMatch[ v[nod][i] ] ] = 0;
            Suport( RightMatch[ v[nod][i] ] );
        }
    }
}
int main(){
    fin >> n >> m;
    for( int i = 1; i <= m; i++ ){
        int a, b;
        fin >> a >> b;
        v[a].push_back( b );
    }
    do{
        memset( f, 0, sizeof(f) );
        ok = 0;
        for( int i = 1; i <= n; i++ )
            if( LeftMatch[i] == 0 && Match( i ) == 1 )
                ok = 1;
    }while( ok == 1 );
    for( int i = 1; i <= n; i++ )
        if( LeftMatch[i] != 0 )
            LeftSuport[i] = 1;
    for( int i = 1; i <= n; i++ )
        if( LeftSuport[i] == 0 )
            Suport( i );
    fout << 2 * n - MatchSize << "\n";
    for( int i = 1; i <= n; i++ ){
        if( LeftSuport[i] == 1 && RightSuport[i] == 1 )
            fout << 0;
        if( LeftSuport[i] == 0 && RightSuport[i] == 1 )
            fout << 1;
        if( LeftSuport[i] == 1 && RightSuport[i] == 0 )
            fout << 2;
        if( LeftSuport[i] == 0 && RightSuport[i] == 0 )
            fout << 3;
        fout << "\n";
    }
    return 0;
}