import java.io.*; import java.util.*; class Main { static ArrayList[] g; static void add(int a, int b, int c){ g[a].add((long)b<<32|c); } @SuppressWarnings("unchecked") public static void main(String[] args) { MyScanner sc = new MyScanner(); out = new PrintWriter(new BufferedOutputStream(System.out)); int n=sc.nextInt(); int[]b=new int[n],c=new int[n]; g=new ArrayList[3*n+2]; Arrays.setAll(g,x->new ArrayList()); for(int i=0;i[] g, long[][] capacity, long[][] flow, int[] level, boolean[] finished, int u, int t, long cur) { if (u == t || cur == 0) return cur; if (finished[u]) return 0; finished[u] = true; for(long e:g[u]){ int dst=(int)(e>>>32); int wei=(int)e; if (level[dst] > level[u]) { long f = augment(g, capacity, flow, level, finished, dst, t, Math.min(cur, capacity[u][dst]-flow[u][dst])); if (f > 0) { flow[u][dst] += f; flow[dst][u] -= f; finished[u] = false; return f; } } } return 0; } // g[i][j] = (dest)<<32|(cap) static long maximumFlow(ArrayList[] g, int s, int t) { int n = g.length; long[][]flow=new long[n][n], cap=new long[n][n]; // adj. matrix for(int u=0;u>>32); int wei=(int)e; cap[u][dst] += wei; } long total = 0; for (boolean cont = true; cont; ) { cont = false; int[] level=new int[n]; Arrays.fill(level, -1); level[s] = 0; // make layered network Queue q=new ArrayDeque(); q.add(s); for (int d = n; q.size()>0 && level[q.peek()] < d; ) { int u=q.poll(); if (u == t) d = level[u]; for(long e:g[u]){ int dst=(int)(e>>>32); int wei=(int)e; if(cap[u][dst]>flow[u][dst] && level[dst] == -1) { q.add(dst); level[dst]=level[u]+1; } } } boolean[] finished=new boolean[n];// make blocking flows for (long f = 1; f > 0; ) { f = augment(g, cap, flow, level, finished, s, t, INF); if (f == 0) break; total += f; cont = true; } } return total; } }