// Arup Guha
// 3/2/2023
// Converted Ford-Fulkerson Code

using namespace std;

#include <bits/stdc++.h>

class ff {
    public:
        ff(int size);
        void add(int v1, int v2, int c);
        int flow();
        int dfs(int v, bool* visited, int min);
        void print();
    private:
        int** cap;
        int n;
        int source;
        int sink;
};

int max(int a, int b);
int min(int a, int b);

int max(int a, int b) {
    return a > b ? a : b;
}

int min(int a, int b) {
    return a < b ? a : b;
}

// Sets up empty object with size nodes, plus source(n-2) and sink(n-1).
ff::ff(int size) {
    n = size+2;
    source = n-2;
    sink = n-1;
    cap = new int*[n];
    for (int i=0;i<n;i++) {
        cap[i] = new int[n];
        for (int j=0; j<n; j++)
            cap[i][j] = 0;
    }
}

// For debugging.
void ff::print() {
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++)
            cout << cap[i][j] << " ";
        cout << endl;
    }
}

// Adds edge with capacity c from v1 to v2.
void ff::add(int v1, int v2, int c) {
    cap[v1][v2] = c;
}

// Wrapper method, returns flow.
int ff::flow() {

    // Set up result.
    bool* visited = new bool[n];
    int res = 0;

    // Keep going as long as there are more augmenting paths.
    while (true) {
        for (int i=0; i<n; i++) visited[i] = false;
        int tmp = dfs(source, visited, 1000000000);
        if (tmp == 0) break;
        res += tmp;
    }

    // Ta da!
    return res;
}

// Recursively returns most flow from vertex v to sink assuming minF flow gets to v.
int ff::dfs(int v, bool* visited, int minF) {

    // We're there, answer is minF.
    if (v == sink) return minF;

    // Skip it...
    if (visited[v]) return 0;

    // Mark and recurse...
    visited[v] = true;
    int flow = 0;

    // Find the next place to go.
    for (int i=0; i<n; i++) {

        // If there's space, recurse.
        if (cap[v][i] > 0) flow = dfs(i, visited, cap[v][i] < minF ? cap[v][i] : minF);

        // If we made it to sink, as rec calls get popped off, update capacities.
        if (flow > 0) {
            cap[v][i] -= flow;
            cap[i][v] += flow;
            return flow;
        }
    }

    // If we get here, we never made it to the sink.
    return 0;
}