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

using namespace std;
int N,M,sol;
int viz[9000],st[9000],dr[9000],d[9000];
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;

 }
}
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);

    }
    solve();

    for(i = 1; i <= N; ++i){
        x = y = 0;
            if(!dr[i]) ++sol;
        if(st[i]){
            sol++;
            x = 1;

        }
        else ++sol,y=1,x=1;
        if(x && y)d[i]=3;
        else if(x) d[i]=2;
        else if(y)d[i]=1;
    }
    printf("%d\n",sol);
    for(i=1;i<=N;++i)
        printf("%d\n",d[i]);
    return 0;
}