#include #include using namespace std; struct edge { int to, avail, rev; }; constexpr int inf = 987'654'321; int N, n; vector> G; vector ptr; vector used; void add_edge(int u, int v, int c) { G[u].push_back(edge{v, c, ptr[v]++}); G[v].push_back(edge{u, 0, ptr[u]++}); } int dfs(int v, int t, int flow) { if(v == t) { return flow; } used[v] = true; for(edge &e : G[v]) { edge &x = G[e.to][e.rev]; if(!used[e.to] && e.avail > 0) { int res = dfs(e.to, t, min(e.avail, flow)); if(res > 0) { e.avail -= res; x.avail += res; return res; } } } return 0; } int max_flow(int s, int t) { int res = 0; for(;;) { used.assign(n, false); int flow = dfs(s, t, inf); if(flow == 0) { return res; } res += flow; } } int main(void) { scanf("%d", &N); ::n = 2 * N + 2; int src = 2 * N, dst = 2 * N + 1; int acc = 0; G.assign(n, vector()); ptr.assign(n, 0); for(int i=0; i