using System; using System.Collections; using System.Collections.Generic; using System.Linq; using System.Text; class TEST{ static void Main(){ Sol mySol =new Sol(); mySol.Solve(); } } class Sol{ public void Solve(){ int V = N*M+2; int src = N*M; int sink = src+1; var Gr = new MaxFlow_Dinic(); Gr.Init(V); int b = 0; int w = 0; int[] dx = new int[]{1,0,-1,0}; int[] dy = new int[]{0,-1,0,1}; Func InRange = (y,x) =>{ return 0<= x && x < M && 0<= y && y < N; }; for(int i=0;iint.Parse(e));} static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));} static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));} } class MaxFlow_Dinic{ // arihon is god class Edge { public int To,Cap,Rev; public Edge(int to = 0,int cap = 0,int rev = 0){ To = to; Cap = cap; Rev = rev; } } List[] G; int[] Level; int[] Iter; static int Inf = (int) 1e9; public int N; public void Init(int n){ N = n; G = new List[N]; for(int i=0;i(); Level = new int[N]; Iter = new int[N]; } public void AddEdge(int from, int to, int cap){ G[from].Add(new Edge(to,cap,G[to].Count)); G[to].Add(new Edge(from,cap,G[from].Count-1)); } void bfs(int s){ for(int j=0;j(); Level[s] = 0; Q.Enqueue(s); while(Q.Count>0){ var v = Q.Dequeue(); foreach(var e in G[v]){ //Console.WriteLine(e.Cap +" "+Level[e.To]); if(e.Cap > 0 && Level[e.To] < 0){ Level[e.To] = Level[v] + 1; Q.Enqueue(e.To); } } } } int dfs(int v,int t,int f){ if(v == t) return f; for(int i = Iter[v]; i 0 && Level[v] < Level[e.To]){ int d = dfs(e.To,t,Math.Min(f,e.Cap)); if(d > 0){ e.Cap -= d; G[e.To][e.Rev].Cap += d; return d; } } } return 0; } public int MaxFlow(int s,int t){ int flow = 0; while(true){ bfs(s); //Console.WriteLine(Level[t]); if(Level[t] < 0) return flow; Iter = new int[N]; int f; while( ( f = dfs(s,t,Inf)) > 0){ flow += f; } } } }