#include <cstdio>
#include <vector>
#define NMAX 8200
using namespace std;

int vizitat[NMAX];
int st[NMAX];
int dr[NMAX];
int sl[NMAX];
int sr[NMAX];
vector < int > Graf[NMAX];
int n,m,nr;

inline void citesc(){

    int x,y;
    freopen("felinare.in","r",stdin);
    freopen("felinare.out","w",stdout);
    scanf("%d%d",&n,&m);
    while(m){
        scanf("%d%d",&x,&y);
        Graf[x].push_back(y);
    --m;
    }
}

bool Hopcroft_Karp(int nod){

    if(vizitat[nod]) return 0;
    vizitat[nod] = 1;
    for(vector < int >::iterator it = Graf[nod].begin();it!=Graf[nod].end();++it)
        if(!dr[*it] || Hopcroft_Karp(dr[*it])){
            st[nod] = *it;
            dr[*it] = nod;
            return 1;
        }
return 0;
}

int suport_minim(int nod){

    for(vector < int >::iterator it = Graf[nod].begin();it!=Graf[nod].end();++it)
        if(!sr[*it]){
            sr[*it] = 1;
            sl[dr[*it]] = 0;
            suport_minim(dr[*it]);
        }
}

inline void solve(){

    bool ok = 1;
        while(ok){

            ok = 0;
            for(register int i=1;i<=n;++i)
                if(!st[i])
                if(Hopcroft_Karp(i)) ok=1,++nr;
        }
    for(register int i=1;i<=n;++i)
        if(st[i]) sl[i] = 1;
    for(register int i=1;i<=n;++i)
        if(!sl[i]) suport_minim(i);

    printf("%d\n",2*n-nr);
    for(register int i=1;i<=n;++i){
        if(!sl[i] && !sr[i])
        printf("3\n");
        else if(!sl[i] && sr[i])
        printf("1\n");
        else  if(sl[i] && !sr[i])
        printf("2\n");
        else printf("0\n");
    }
}

int main(){

    citesc();
    solve();

return 0;
}