int len=1;
void add(int x,int y,LL CA)
{
  pre[++len]=last[x];last[x]=len;e[len]=y;ca[len]=CA;
  pre[++len]=last[y];last[y]=len;e[len]=x;ca[len]=0;
}
int aug(int u,int m)
{
  if (u==target) return m;
  int f=m,td=NC;
  for(int p=last[u];p;p=pre[p])
   if (ca[p])
   {
     int v=e[p];
     if (dis[u]==dis[v]+1)
     {
       int tmp=aug(v,min(f,ca[p]));
       ca[p]-=tmp,ca[p^1]+=tmp,f-=tmp;
       if (!f||dis[source]==NC) return m-f;
     }
     td=min(td,dis[v]+1);
   }
  if (f==m)
  {
    if (!--gap[dis[u]]) dis[source]=NC;
    gap[dis[u]=td]++;
  }
  return m-f;
}
int sap()
{
  memset(gap,0,sizeof(gap));
  memset(dis,0,sizeof(dis));
  int ans=0;gap[0]=NC;
  while(dis[source]<NC)ans+=aug(source,inf);
  return ans;
}