#include<fstream>
#include<cstring>
#include<vector>
using namespace std;
const int NMAX = 8200;

vector<int> G[NMAX];
vector<int>::iterator it;
bool u[NMAX];
int l[NMAX],r[NMAX];
int f1[NMAX],f2[NMAX];

int pairUp(int n){
     if(u[n]) return 0;
     u[n]=1;
     
     for(it=G[n].begin();it!=G[n].end();++it)
       if(!r[*it])
       {
           l[n]=(*it);
           r[*it]=n;
           return 1;         
       }
     for(it=G[n].begin();it!=G[n].end();++it)
       if(pairUp(r[*it]))
       {
           l[n]=(*it);
           r[*it]=n;
           return 1;         
       }   
     return 0;
}

int main(){
    ifstream f("felinare.in");
    ofstream g("felinare.out");
    int N,M,i,x,y,ok;
    
    f>>N>>M;
    
    for(i=1;i<=M;++i)
    {
      f>>x>>y;
      G[x].push_back(y);                 
    }
    
    ok=1;
    while(ok)
    {
      ok=0;
      memset(u,0,sizeof(u));
      for(i=1;i<=N;++i)
        if(!l[i]) ok|=pairUp(i);
      
     }
    
    for(i=1;i<=N;++i)
    {
      f1[i]=1;
      f2[i]=2;                 
    }
    
    for(i=1;i<=N;++i)
      if(l[i]) f1[i]=0;
      
    int sm=0;
    
    for(i=1;i<=N;++i) sm+=(f1[i]>0)+(f2[i]>0);
    g<<sm<<'\n';
    for(i=1;i<=N;++i)
      g<<(f1[i]+f2[i])<<'\n';
    
 return 0;   
}