#include <iostream>
#include <vector>
using namespace std;

struct Edge {
    int from;
    int to;
    int capacity;
    int flow;

    int other(int vertex) {
        if (vertex == from) {
            return to;
        } else {
            return from;
        }
    }
    int capacity_to(int vertex) {
        if (vertex == from) {
            return flow;
        } else {
            return capacity - flow;
        }
    }
    void add_flow_to(int vertex, int delta_flow) {
        if (vertex == from) {
            flow -= delta_flow;
        } else {
            flow += delta_flow;
        }
    }
};

struct Graph {
    vector<Edge> edges;
    vector<vector<int>> graph;
    vector<bool> used;
    vector<int> previous_edge_index;

    Graph(int vertex_count) {
        graph.resize(vertex_count);
    }

    void add_edge(int from, int to, int capacity) {
        edges.push_back({from, to, capacity, 0});
        graph[from].push_back(edges.size() - 1);
        graph[to].push_back(edges.size() - 1);
    }

    void dfs(int v) {
        used[v] = true;
        for (int edge_index : graph[v]) {
            int to = edges[edge_index].other(v);
            if (!used[to] && edges[edge_index].capacity_to(to)) {
                previous_edge_index[to] = edge_index;
                dfs(to);
            }
        }

    }

    bool check_path(int source, int sink) {
        used.assign(graph.size(), false);
        previous_edge_index.assign(graph.size(), -1);
        dfs(source);
        return used[sink];
    }
    int get_bottle_neck(int source, int sink) {
        int v = sink;
        int res = 1e9;
        while (v != source) {
            int prev_e = previous_edge_index[v];
            int prev_v = edges[prev_e].other(v);
            res = min(res,edges[prev_e].capacity_to(v));
            v = prev_v;
        }
        return res;
    }
    void add_flow(int source, int sink,int delta){
        int v = sink;
        while (v != source) {
            int prev_e = previous_edge_index[v];
            int prev_v = edges[prev_e].other(v);
            edges[prev_e].add_flow_to(v,delta);
            v = prev_v;
        }
    }


    int max_flow(int source, int sink){
        int res = 0;
        while(check_path(source,sink)){
            int bottle_n = get_bottle_neck(source,sink);
            res += bottle_n;
            add_flow(source,sink,bottle_n);
        }
        return res;
    }
};