#pragma once
/**
* Author: Teetat T.
* Date: 2024-07-15
* Description: Dinic's Algorithm for finding the maximum flow.
* Time: O(V E \log U) where U is the maximum flow.
*/template<classT,booldirected=true,boolscaling=true>structDinic{staticconstexprTINF=numeric_limits<T>::max()/2;structEdge{intto;Tflow,cap;Edge(int_to,T_cap):to(_to),flow(0),cap(_cap){}Tremain(){returncap-flow;}};intn,s,t;TU;vector<Edge>e;vector<vector<int>>g;vector<int>ptr,lv;boolcalculated;Tmax_flow;Dinic(){}Dinic(intn,ints,intt){init(n,s,t);}voidinit(int_n,int_s,int_t){n=_n,s=_s,t=_t;U=0;e.clear();g.assign(n,{});calculated=false;}voidadd_edge(intfrom,intto,Tcap){assert(0<=from&&from<n&&0<=to&&to<n);g[from].emplace_back(e.size());e.emplace_back(to,cap);g[to].emplace_back(e.size());e.emplace_back(from,directed?0:cap);U=max(U,cap);}boolbfs(Tscale){lv.assign(n,-1);vector<int>q{s};lv[s]=0;for(inti=0;i<(int)q.size();i++){intu=q[i];for(intj:g[u]){intv=e[j].to;if(lv[v]==-1&&e[j].remain()>=scale){q.emplace_back(v);lv[v]=lv[u]+1;}}}returnlv[t]!=-1;}Tdfs(intu,intt,Tf){if(u==t||f==0)returnf;for(int&i=ptr[u];i<(int)g[u].size();i++){intj=g[u][i];intv=e[j].to;if(lv[v]==lv[u]+1){Tres=dfs(v,t,min(f,e[j].remain()));if(res>0){e[j].flow+=res;e[j^1].flow-=res;returnres;}}}return0;}Tflow(){if(calculated)returnmax_flow;calculated=true;max_flow=0;for(Tscale=scaling?1LL<<(63-__builtin_clzll(U)):1LL;scale>0;scale>>=1){while(bfs(scale)){ptr.assign(n,0);while(true){Tf=dfs(s,t,INF);if(f==0)break;max_flow+=f;}}}returnmax_flow;}pair<T,vector<int>>cut(){flow();vector<int>res(n);for(inti=0;i<n;i++)res[i]=(lv[i]==-1);return{max_flow,res};}};
#line 2 "flow/dinic.hpp"
/**
* Author: Teetat T.
* Date: 2024-07-15
* Description: Dinic's Algorithm for finding the maximum flow.
* Time: O(V E \log U) where U is the maximum flow.
*/template<classT,booldirected=true,boolscaling=true>structDinic{staticconstexprTINF=numeric_limits<T>::max()/2;structEdge{intto;Tflow,cap;Edge(int_to,T_cap):to(_to),flow(0),cap(_cap){}Tremain(){returncap-flow;}};intn,s,t;TU;vector<Edge>e;vector<vector<int>>g;vector<int>ptr,lv;boolcalculated;Tmax_flow;Dinic(){}Dinic(intn,ints,intt){init(n,s,t);}voidinit(int_n,int_s,int_t){n=_n,s=_s,t=_t;U=0;e.clear();g.assign(n,{});calculated=false;}voidadd_edge(intfrom,intto,Tcap){assert(0<=from&&from<n&&0<=to&&to<n);g[from].emplace_back(e.size());e.emplace_back(to,cap);g[to].emplace_back(e.size());e.emplace_back(from,directed?0:cap);U=max(U,cap);}boolbfs(Tscale){lv.assign(n,-1);vector<int>q{s};lv[s]=0;for(inti=0;i<(int)q.size();i++){intu=q[i];for(intj:g[u]){intv=e[j].to;if(lv[v]==-1&&e[j].remain()>=scale){q.emplace_back(v);lv[v]=lv[u]+1;}}}returnlv[t]!=-1;}Tdfs(intu,intt,Tf){if(u==t||f==0)returnf;for(int&i=ptr[u];i<(int)g[u].size();i++){intj=g[u][i];intv=e[j].to;if(lv[v]==lv[u]+1){Tres=dfs(v,t,min(f,e[j].remain()));if(res>0){e[j].flow+=res;e[j^1].flow-=res;returnres;}}}return0;}Tflow(){if(calculated)returnmax_flow;calculated=true;max_flow=0;for(Tscale=scaling?1LL<<(63-__builtin_clzll(U)):1LL;scale>0;scale>>=1){while(bfs(scale)){ptr.assign(n,0);while(true){Tf=dfs(s,t,INF);if(f==0)break;max_flow+=f;}}}returnmax_flow;}pair<T,vector<int>>cut(){flow();vector<int>res(n);for(inti=0;i<n;i++)res[i]=(lv[i]==-1);return{max_flow,res};}};