#include <fstream>
#include <vector>
#include <cstring>
#define dim 20005
using namespace std;
ifstream fin("felinare.in");
ofstream fout("felinare.out");
int n,i,m,j,Left[dim],Right[dim],viz[dim],a,b,ok,sol,sl[dim],sr[dim];
vector <int> v[dim];
int cuplaj(int nod){
    viz[nod]=1;
    for(int i=0; i<v[nod].size();i++){
        int vecin = v[nod][i];
        if(Right[vecin]==0){
            Left[nod]=vecin;
            Right[vecin]=nod;
            return 1;
        }
    }
    for(int i=0;i<v[nod].size();i++){
        int vecin = v[nod][i];
        if(viz[Right[vecin]]==0 && cuplaj(Right[vecin])){
            Left[nod]=vecin;
            Right[vecin]=nod;
            return 1;
        }
    }
    return 0;
}
void suport(int nod){

    for(int i=0;i<v[nod].size();i++){
        int vecin = v[nod][i];
        if(sr[vecin]==0){
            sr[vecin]=1;
            sl[Right[vecin]]=0;
            suport(Right[vecin]);
        }
    }

}
int main(){
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>a>>b;
        v[a].push_back(b+n);
    }
    ok=1;

    while(ok==1){
        ok=0;
        memset(viz,0,sizeof(viz));
        for(i=1;i<=n;i++){
            if(Left[i]==0 && cuplaj(i)){
                sol++;
                ok=1;
            }
        }
    }
    fout<<2*n-sol<<"\n";
    for(i=1;i<=n;i++){
        if(Left[i]!=0){
            sl[i]=1;
        }
    }
    for(i=1;i<=n;i++){
        if(sl[i]==0){
            suport(i);
        }
    }
    for(i=1;i<=n;i++){
        if(sl[i]==1 && sr[i+n]==1){
            fout<<0<<"\n";
        }
        if(sl[i]==0 && sr[i+n]==1){
            fout<<1<<"\n";
        }
        if(sl[i]==1 && sr[i+n]==0){
            fout<<2<<"\n";
        }
        if(sl[i]==0 && sr[i+n]==0){
            fout<<3<<"\n";
        }
    }

    return 0;
}