#include<stdio.h>
#include<string.h>
#define N 8200
int n,m,*a[N],st[N],dr[N],viz[N],nr,i,x,y,s1[N],s2[N];
int cupleaza(int nod)
{int i;
 if(viz[nod]) return 0;
 viz[nod]=1;
 for(i=1;i<=a[nod][0];i++)
  if(!dr[a[nod][i]] || cupleaza(dr[a[nod][i]]))
    {st[nod]=a[nod][i];
     dr[a[nod][i]]=nod;
     return 1;}
 return 0;}

void cuplaj()
{for(i=1;i<=n;i++)
  if(!st[i])
   if(cupleaza(i)) nr++;
   else{
     memset(viz,0,sizeof(viz));
     if(cupleaza(i)) nr++;}
 }

void adauga(int nod)
{if(!nod) return;
 int i;
 for(i=1;i<=a[nod][0];i++)
  if(!s2[a[nod][i]])
  {s2[a[nod][i]]=1;
   s1[st[a[nod][i]]]=0;
   adauga(st[a[nod][i]]);}
 }

void suport()
{for(i=1;i<=n;i++)
  if(st[i]) s1[i]=1;
 for(i=1;i<=n;i++)
  if(!st[i]) adauga(i);}

void citire()
{freopen("felinare.in","r",stdin);
 scanf("%d %d",&n,&m);
 for(i=1;i<=m;i++) {scanf("%d %d",&x,&y);viz[x]++;}
 fclose(stdin);
 for(i=1;i<=n;i++)
  {a[i]=new int[viz[i]+2];
   a[i][0]=0;}
 freopen("felinare.in","r",stdin);
 scanf("%d %d",&n,&m);
 for(i=1;i<=m;i++) {scanf("%d %d",&x,&y);a[x][++a[x][0]]=y;}
 memset(viz,0,sizeof(viz));}

int main()
{freopen("felinare.out","w",stdout);
 citire();
 cuplaj();
 suport();
 printf("%d\n",2*n-nr);
 for(i=1;i<=n;i++)
  printf("%d\n",(!s1[i])^(2*!s2[i]));
 fclose(stdout);
 return 0;}