#include<stdio.h>
#include<vector>
#define pb push_back
#define maxn 8200
using namespace std;

int n,m,nr,mm,mvc,mis;
int left[maxn],right[maxn];
int v[maxn],L[maxn],R[maxn];
vector <int> l[maxn];

void read()
{
    int x,y;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        l[x].pb(y);
    }
}

int pair_up(int k)
{
    if(v[k]==nr) return 0;
    v[k]=nr;
    for(unsigned int i=0;i<l[k].size();i++)
     if(!right[l[k][i]] || pair_up(right[l[k][i]]))
     {
         left[k]=l[k][i]; right[l[k][i]]=k;
         return 1;
     }
    return 0;
}

void MMatch()
{
    int ok,i;
    for(ok=1,nr=1;ok;nr++)
    {
        ok=0;
        for(i=1;i<=n;i++)
         if(!left[i] && pair_up(i))
          mm++,ok=1;
    }
}

void match(int k)
{
    for(unsigned int i=0;i<l[k].size();i++)
     if(L[right[l[k][i]]])
     {
         L[right[l[k][i]]]=0; R[l[k][i]]=1;
         match(right[l[k][i]]);
     }
}

void MVC()
{
    for(int i=1;i<=n;i++) if(left[i]) L[i]=1;
    for(int i=1;i<=n;i++) if(!left[i]) match(i);
}

void MIS()
{
    for(int i=1;i<=n;i++)
    {
        L[i]=!L[i]; R[i]=!R[i];
        if(L[i]) mis++;
        if(R[i]) mis++;
    }
}

void print()
{
    printf("%d\n",mis);
    for(int i=1;i<=n;i++)
     if(!L[i] && !R[i]) printf("0\n");
     else
      if(L[i] && R[i]) printf("3\n");
      else
      if(L[i]) printf("1\n");
       else printf("2\n");
}

int main()
{
    freopen("felinare.in","r",stdin);
    freopen("felinare.out","w",stdout);

    read();
    MMatch();
    MVC();
    MIS();
    print();

    fclose(stdin);
    fclose(stdout);
    return 0;
}