// suport minim in graf bipartit + algoritm complet de cuplaj maxim

#include<stdio.h>
struct Nod {
    int val;
    Nod *next;
};
Nod *a[8200];
int use[8200];
int n;
int sl[8200];
int sr[8200];
int m;
int ok;
int nrcupl;
int x;
int y;
int l[8200];
int r[8200];
void insert(Nod *&u, int k)
{
    Nod *v = new Nod;
    v -> val = k;
    v -> next = u;
    u = v;
}
int PrUp(int nod)
{
    if (use[nod]) return 0;
    use[nod] = 1;
    for(Nod *it = a[nod]; it; it = it -> next)
     if (!l[it->val])
       {
           l[it->val] = nod;
           r[nod] = it->val;
           sl[nod] = 1;
           return 1;
       }
    for(Nod *it = a[nod]; it; it = it -> next)
     if (PrUp(l[it->val]))
       {
           l[it->val] = nod;
           r[nod] = it->val;
           sl[nod] = 1;
           return 1;
       }
    return 0;
}

inline void support(int n)
 {

     for(Nod *it =a[n]; it; it = it -> next)
      if(!sr[it->val]) // daca nu e in suport
           {
            sr[it->val]=1;
            sl[l[it->val]]=0;
            support(l[it->val]);
          }
 }
int main()
{
    freopen("felinare.in","r",stdin);
    freopen("felinare.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(int i = 1; i <= m; i++)
    {
     scanf("%d %d",&x,&y);
     insert(a[x],y);
    }
    ok = 1;
    while (ok)
     {
         ok = 0;
         for(int i = 1; i <= n; i++)
          use[i] = 0;
         for(int i = 1; i <= n; i++)
          if (!r[i])
           if (PrUp(i))
            ok = ++nrcupl;
     }
    printf("%d\n",2 * n - nrcupl);
    for(int i = 1; i <= n; i++)
     if (!sl[i]) support(i);
    for(int i = 1; i <= n; i++)
     {
         int x = sl[i];
         int y = sr[i];
        printf("%d\n",1 - x + 2 *(1 - y));
     }

    return 0;
}