bool bfs(){

	memset(deep,0,sizeof(deep));

	queue<int>que;

	que.push(s);

	deep[s]=1;

	while(!que.empty()){

		int u=que.front();

		que.pop();

		for(int i=head[u];i!=-1;i=e[i].nextt){

			int v=e[i].v;

			if(e[i].w>0&&deep[v]==0){

				deep[v]=deep[u]+1;

				if(v==t)

					return true;

				que.push(v);

			}

		}

	}

	return deep[t]==0?false:true;

}

int dfs(int u,int fl){

	if(u==t)

		return fl;

	int ans=0,x=0;

	for(int i=cur[u];i!=-1;i=e[i].nextt){

		int v=e[i].v;

		if(e[i].w>0&&deep[v]==deep[u]+1){

			x=dfs(v,min(e[i].w,fl-ans));

			e[i].w-=x;

			e[i^1].w+=x;

			if(e[i].w)

				cur[u]=i;

			ans+=x;

			if(ans==fl)

				return ans;

		}

	}

	if(ans==0)

		deep[u]=0;

	return ans;

}

int dinic(int n){

	int ans=0;

	while(bfs()){

		for(int i=0;i<=n;i++)

			cur[i]=head[i];

		ans+=dfs(s,inf);

	}

	return ans;

}