#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

const int nmax = 8200;
vector<int> ms[nmax * 2], md[nmax * 2];
int n, cup[nmax * 2];

bool viz[nmax * 2], ma[nmax * 2],lu[nmax*2];

bool solv(int x)
{
  if (viz[x]==1)
    return 0;
  viz[x]=1;
  int i;
  for(i=ms[x].size()-1;i>=0;i--)
    if(cup[ms[x][i]]==0) {
      cup[ms[x][i]]=x;
      cup[x]=ms[x][i];
      return 1;
    }
  for(i=ms[x].size()-1;i>=0;i--)
    if(solv(cup[ms[x][i]])) {
      cup[ms[x][i]]=x;
      cup[x]=ms[x][i];
      return 1;
    }
  return 0;
}

void dfd(int x);

void dfs(int x)
{
  if (ma[x] == 0) {
    ma[x] = 1;
    int i;
    for(i = ms[x].size() - 1; i >= 0; i--)
      if(cup[x] != ms[x][i]) {
        dfd(ms[x][i]);
      }
  }
}

void dfd(int x)
{
  if(ma[x] == 0) {
    ma[x] = 1;
    dfs(cup[x]);
  }
}


int main()
{
    freopen("felinare.in","r",stdin);
    freopen("felinare.out","w",stdout);
    int m,i,j,x,y,nr=0;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        ms[x+n].push_back(y);
        md[y].push_back(x+n);
    }
    for(i=n+1;i<=n*2;i++)
        if(cup[i]==0)
    {
        for(j=n+1;j<=n*2;j++)
            viz[j]=0;
        nr+=solv(i);
    }

    for(i=n+1;i<=n*2;i++)
      if(cup[i]==0)
        dfs(i);
  printf("%d\n",n*2-nr);
  for(i = 1; i <= n; i++)
    lu[i] =  ma[i];
  for(i = n + 1; i <= n * 2; i++)
    lu[i] = 1-ma[i];
  for(i=1;i<=n;i++) {
    //printf("%d: %d %d\n",i,ma[i+n],ma[i]);
    if (lu[i]!=0 && lu[i+n]!=0)
      printf("0\n");
    else if (lu[i]!=0 && lu[i+n]==0)
      printf("1\n");
    else if(lu[i]==0 && lu[i+n]!=0)
      printf("2\n");
    else // if(lu[i]==0 && lu[i+n]==0)
      printf("3\n");
  }
  return 0;
}