#include <fstream>
#include <cstring>
#include <bitset>
#include <cmath>
#include <list>
#define DIM 16200
using namespace std;
ifstream f("felinare.in");
ofstream g("felinare.out");
int n,m;
int L[DIM],R[DIM],viz2[DIM];

list<int> C[DIM];
bitset<DIM> VL,VR,viz;

inline bool cuplaj(int nod){
    list<int>::iterator it;
    //prima incercare
    viz[nod]=1;
    for(it=C[nod].begin();it!=C[nod].end();it++){
        if(R[*it]==0){
            R[*it]=nod;
            L[nod]=*it;
            return true;
        }
    }
    //a doua incercare
    viz2[nod]++;
    if(viz2[nod]>sqrt(n))
        return 0;
    for(it=C[nod].begin();it!=C[nod].end();it++){
        if(!viz[nod]&& R[*it]!=nod && cuplaj(R[*it])){
            R[*it]=nod,L[nod]=*it;
            return true;
        }
    }
    return false;
}

void suport(int nod){
    list<int>::iterator it;
    for(it=C[nod].begin();it!=C[nod].end();it++){
        if(VR[*it]==0){
            VR[*it]=1;
            VL[R[*it]]=0;
            suport(R[*it]);
        }
    }
}

int main(void){
    register int i,j,x,y,nr=0;
    bool ok,q;

    f>>n>>m;
    for(i=1;i<=m;i++){
        f>>x>>y;
        C[x].push_back(y);
    }

    //cuplaj maxim
    do{ok=false;
        for(i=1;i<=n;i++){
            viz2[i]=0;
            if(!L[i]){
                q=cuplaj(i);
                if(q)
                    ok=true;
            }
        }
        viz.reset();
    }while(ok);

    for(i=1;i<=n;i++)
        if(L[i]) nr++,VL[i]=1;
    g<<n*2-nr<<"\n";

    //suport minim
    for(i=1;i<=n;i++){
        if(VL[i]==0)
            suport(i);
    }
    for(i=1;i<=n;i++){
        if(VL[i]==0 && VR[i]==0) g<<"3\n";
        else if(VL[i]==0 && VR[i]==1) g<<"1\n";
        else if(VL[i]==1 && VR[i]==0) g<<"2\n";
        else g<<"0\n";
    }

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