#include <cstdio>
#include <vector>
#include <cstring>
#define nmax 20005

using namespace std;
int N,M,sol;
int viz[9000*2],st[9000*2],dr[9000*2];
vector<int>G[nmax];
inline bool Cupleaza(int nod){
 if(viz[nod]) return false;

  for(auto it:G[nod])
    if(!dr[it]){
      dr[it] = nod;
      st[nod] = it;
      return true;
  }
  viz[nod] = 1;
  for(auto it:G[nod])
   if(Cupleaza(dr[it])){
     st[nod] = it;
     dr[it] = nod;
     return true;
  }
  return false;
}

inline void solve(){
 int gata = 1,i;
 while(gata){
    gata = 0;
    memset(viz,0,sizeof(viz));
    for(i = 1; i <= N; ++i)
      if(!st[i]&&Cupleaza(i))
        gata = 1,++sol;

 }
}
inline void MVC(int nod){
 for(auto it:G[nod])
    if(!viz[it]){
      viz[it] = 1;
      viz[dr[it]] = 0;
      MVC(dr[it]);
 }
}
int main(){
    int i,x,y;
    freopen("felinare.in","r",stdin);
    freopen("felinare.out","w",stdout);
    scanf("%d %d\n",&N,&M);
    for(i = 1; i <= M; ++i){
        scanf("%d %d\n",&x,&y);
        G[x].push_back(y+N);
        G[y+N].push_back(x);
    }
    solve();
    memset(viz,0,sizeof(viz));
    printf("%d\n",2*N-sol);
    for(i = 1; i <= N; ++i)
        if(st[i]) viz[i] = 1;
    for(i = 1; i <= N; ++i)
        if(!st[i]) MVC(i);
    for(i = 1; i <= N; ++i)
        if(viz[i]){
            if(viz[i+N]) printf("0\n");
              else printf("2\n");
    }
        else{
             if(viz[i+N]) printf("1\n");
               else printf("3\n");
        }
    return 0;
}