#include<fstream>
#include<cstring>
using namespace std;
typedef struct celula{
          int nod;
          celula *next;
          }*lista;
lista graf[8200],v;
int i,n,m,x,y,l[8200],r[8200],st[16400];
bool viz[8200];

bool cupleaza(int nod) {
       if(viz[nod]==1) return 0;
      viz[nod]=1;
       for(lista p=graf[nod]; p; p=p->next)
             if(!r[p->nod]){
                l[nod]=p->nod;
                 r[p->nod]=nod;
                return 1;
               }
       for(lista p=graf[nod]; p; p=p->next)
             if(cupleaza(r[p->nod])) {
                          l[nod]=p->nod;
                           r[p->nod]=nod;
                          return 1;
                          }
       return 0;
}
     
void solve(int nod) {
     for (lista p=graf[nod]; p; p=p->next)
      if (st[n+p->nod]==0) {
                           st[n+p->nod]=1;
                           st[r[p->nod]]=0;
                           solve(r[p->nod]);
                           }
}

int main(void) {
    ifstream fin("felinare.in");
    ofstream fout("felinare.out");
    fin>>n>>m;
    for (i=1; i<=m; ++i) {
            fin>>x>>y;
            v=new celula; v->nod=y; v->next=graf[x]; graf[x]=v;
            }
    bool ok=1;
    while (ok) {
            ok=0; memset(viz,0,sizeof(viz));
            for (i=1; i<=n; ++i)
             if (l[i]==0) ok|=cupleaza(i);
             }
    int cuplaj=0;
    for (i=1; i<=n; ++i)
     if (l[i]>0){ ++cuplaj; st[i]=1; }
    for (i=1; i<=n; ++i)
     if (l[i]==0) solve(i);
    fout<<2*n-cuplaj<<"\n";
    
    for (i=1; i<=n; ++i)
     if (st[i]==0&&st[n+i]==0) fout<<"3\n";
      else if (st[i]==1&&st[n+i]==1) fout<<"0\n";
       else if (st[i]==1) fout<<"2\n";
        else fout<<"1\n";
 return(0);
}