#include<stdio.h>
#include<string.h>
FILE *f,*g;
int viz[1001],a[1001][1001],flux,n,x,min,parinte[1001],m,i,y,c;
int df(int k)
{ int i; viz[k]=1;
  for(i=1;i<=n;i++) if(a[k][i]&&!viz[i]&&!parinte[i]) { parinte[i]=k; df(i); }
  if(parinte[n]) return 1; return 0;
}
void main()
{ f=fopen("ff.in","r"); g=fopen("ff.out","w");
  fscanf(f,"%d%d",&n,&m);
  for(i=1;i<=m;i++) { fscanf(f,"%d%d",&x,&y); a[x][y]=1; }
  while(df(1))
      { x=n; min=111000;
	while(x!=1)
	 { if(a[parinte[x]][x]<min) min=a[parinte[x]][x];
	   x=parinte[x];
	 }
	x=n; flux+=min;
	while(x!=1)
	 { a[parinte[x]][x]-=min;
	   a[x][parinte[x]]+=min;
	   x=parinte[x];
	 }
	memset(parinte,0,sizeof(parinte)); memset(viz,0,sizeof(viz));
      }
  fprintf(g,"%d",flux); fclose(g);
}