#include <iostream>
#include <fstream>
#include <bitset>
#include <vector>

#define DN 9005
#define next_nod list[nod][i]
#define un unsigned
using namespace std;

ifstream f("felinare.in");
ofstream g("felinare.out");

vector < int > list[DN];
bitset < DN > viz;

int n,m,l[DN],r[DN],sl[DN],sr[DN],rez=0;

void read(){

    f>>n>>m;
    for(;m--;){

        int a,b;
        f>>a>>b;
        list[a].push_back(b);
    }
}

bool cupleaza(int nod){

    if(viz[nod])
        return false;
    viz[nod] = true;
    for(un int i=0;i<list[nod].size();++i)
        if( !r[next_nod] || cupleaza(r[next_nod])){

            l[nod] = next_nod;
            r[next_nod] = nod;
            return true;
        }
    return false;
}

void suport(int nod){

    for(un int i=0;i<list[nod].size();++i)
        if(!sr[ next_nod ]){

            sr[ next_nod ] = 1;
            sl[ r[next_nod] ] = 0;
            suport( r[next_nod] );
        }
}

void solve(){

    /// cuplaj
    bool exista_cuplaj = true;
    for( ; exista_cuplaj ;){

        exista_cuplaj = false;
        viz&=0;
        for(int i=1;i<=n;++i)
            if(!l[i])
                exista_cuplaj|=cupleaza(i);
    }
    /// suport minim
    for(int i=1;i<=n;++i)
        if(l[i])
            sl[i] = 1;
    for(int i=1;i<=n;++i)
        if(!sl[i]) suport(i);

    for(int i=1;i<=n;++i){
        rez+=!sl[i];
        rez+=!sr[i];
    }
}
void write(){

    g<<rez<<"\n";

    for(int i=1;i<=n;++i)
        g << ( 1 - sl[i] + 2 * (1 - sr[i]))<<"\n";

}


int main()
{
    read();
    solve();
    write();

    return 0;
}