#include<iostream>
#include<vector>
#include<deque>
#include<limits>
#include<algorithm>


struct FordFulkersonGraph {
    struct Arc {
        int start_;
        int end_;
        int flow_;
        int capacity_;
        
        int get_dest(int from) {  // Return the destination node if we were to traverse the arc from node `from`
            if(from == start_) {
                return end_;
            } else {
                return start_;
            }
        }
        
        void add_flow(int from, int to_add) {  // Adds flow from originating vertex `from`
            if(from == start_) {
                flow_ += to_add;
            } else {
                flow_ -= to_add;
            }
        }
        
        int get_capacity(int from) {  // Gets the capacity of the edge if the originating vertex is `from`
            if(from == start_) {
                return capacity_ - flow_;
            } else {
                return flow_;
            }
        }
    };
    
    struct Node {
        int index;
        std::vector<Arc*> connected_arcs_;  // Arcs (directed edges) that start and end in this node
    };
    
    std::vector<Node> nodes_;
    std::deque<Arc> arcs_;  // We use deque here to prevent pointer invalidation on reallocation
    
    void add_node() {
        nodes_.push_back({(int)nodes_.size(), {}});
    }
    
    void add_edge(int start, int end, int capacity) {
        arcs_.push_back({start, end, 0, capacity});
        nodes_[start].connected_arcs_.push_back(&arcs_.back());
        nodes_[end].connected_arcs_.push_back(&arcs_.back());
    }
    
    int _push_augmenting_path_dfs(int pos, int end, int to_push, std::vector<bool> *explr = NULL) {
        if(explr == NULL) {
            explr = new std::vector<bool>(nodes_.size(), false);
        }
        if(pos == end) {
            return to_push;
        }
        
        explr->at(pos) = true;
        for(Arc* arc : nodes_[pos].connected_arcs_) {
            int dest = arc->get_dest(pos);
            int arc_capacity = arc->get_capacity(pos);
            if(!explr->at(dest) && arc_capacity > 0) {
                // Recursively find if we can push flow through any of the connected nodes
                int amount_pushed = _push_augmenting_path_dfs(dest, end, std::min(arc_capacity, to_push), explr);
                if(amount_pushed > 0) {
                    arc->add_flow(pos, amount_pushed);
                    return amount_pushed;
                }
            }
        }
        return 0;  // Failed to push flow towards destination in any direction
    }
    
    int compute_flow(int start, int end) {
        int result = 0;
        int amount_pushed;
        do {
            amount_pushed = _push_augmenting_path_dfs(start, end, std::numeric_limits<int>::max());
            result += amount_pushed;
        } while(amount_pushed > 0);
        return result;
    }
};


int main() {
    // Construct a simple flow network and find the max-flow on it
    FordFulkersonGraph graph;
    for(int i=0; i<6; i++) graph.add_node();
    graph.add_edge(0, 1, 2);
    graph.add_edge(1, 4, 2);
    graph.add_edge(4, 5, 2);
    graph.add_edge(1, 2, 1);
    graph.add_edge(2, 5, 1);
    graph.add_edge(0, 3, 1);
    graph.add_edge(3, 4, 1);
    int result = graph.compute_flow(0, 4);
    std::cout << result << '\n';
    return 0;
}