const int INF=0xfffffff ;
struct node{
    int s,t,cap,nxt ;
}e[200005] ;
int m,n,head[10005],level[10005],cnt ;
void add(int s,int t,int cap)
{
    e[cnt].s=s ;e[cnt].t=t ;e[cnt].cap=cap ;e[cnt].nxt=head[s] ;head[s]=cnt++ ;
    e[cnt].s=t ;e[cnt].t=s ;e[cnt].cap=0 ;e[cnt].nxt=head[t] ;head[t]=cnt++ ;
}
bool build(int s,int t)
{
    memset(level,-1,sizeof(level)) ;
    queue <int> q ;
    level[s]=0 ;
    q.push(s) ;
    while(!q.empty())
    {
        int u=q.front() ;
        q.pop() ;
        for(int i=head[u] ;i!=-1 ;i=e[i].nxt)
        {
            int tt=e[i].t ;
            if(level[tt]==-1 && e[i].cap>0)
            {
                level[tt]=level[u]+1 ;
                if(tt==t)return true ;
                q.push(tt) ;
            }
        }
    }
    return false ;
}
int find(int s,int t,int flow)
{
    if(s==t)return flow ;
    int ret=0,a ;
    for(int i=head[s] ;i!=-1 ;i=e[i].nxt)
    {
        int tt=e[i].t ;
        if(level[tt]==level[s]+1 && e[i].cap>0 && (a=find(tt,t,min(flow,e[i].cap))))
        {
            e[i].cap-=a ;
            e[i^1].cap+=a ;
            return a ;
        }
    }
    return 0 ;
}
int dinic(int s,int t)
{
    int flow,ret=0 ;
    while(build(s,t))
        while(flow=find(s,t,INF))
            ret+=flow ;
    return ret ;
}