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


struct DinicFlowNetwork {
    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_;
    };
    
    std::vector<Node> nodes_;
    std::deque<Arc> arcs_;
    
    void add_node() {
        nodes_.push_back({int(nodes_.size()), {}});
    }
    
    void add_arc(int start, int end, int capacity, int flow = 0) {
        arcs_.push_back({start, end, flow, capacity});
        nodes_[start].connected_arcs_.push_back(&arcs_.back());
        nodes_[end].connected_arcs_.push_back(&arcs_.back());
    }
    
    int compute_flow(int source_i, int sink_i) {  // Compute the maximum flow with the Dinic's algorithm
        int result = 0;
        while(1) {
            // First divide into layers with a breadth-first search
            std::vector<int> level(nodes_.size(), -1);
            {
                std::deque<std::tuple<int, int> > queue(1, std::make_tuple(0, source_i) );
                level[source_i] = 0;
                
                while(queue.size() > 0) {
                    int cur_level;
                    int cur_node_i;
                    std::tie(cur_level, cur_node_i) = queue.front();  // Extract the values from queue
                    queue.pop_front();
                    
                    for(Arc* arc : nodes_[cur_node_i].connected_arcs_) if(arc->get_capacity(cur_node_i) > 0) {
                        int next_i = arc->get_dest(cur_node_i);
                        if(level[next_i] == -1) {
                            level[next_i] = cur_level+1;
                            queue.push_back(std::make_tuple(cur_level+1, next_i));
                        }
                    }
                }
                
                if(level[sink_i] == -1) {
                    return result;  // Path to sink no longer exists, so return
                }
            }
            
            // Now perform DFS to push through the blocking flow
            // Since due to leveling we never push back flow, we can speed up DFS by remembering arc iteration indices
            std::vector<int> arc_index(nodes_.size(), 0);
            
            std::function<int (int, int)> dfs = [&](int cur_i, int capacity) {
                if(cur_i == sink_i) {
                    return capacity;
                }
                
                for(int& i = arc_index[cur_i]; i < (int)nodes_[cur_i].connected_arcs_.size(); i++) {
                    Arc* arc = nodes_[cur_i].connected_arcs_[i];
                    int next_i = arc->get_dest(cur_i);
                    if(arc->get_capacity(cur_i) > 0 && level[cur_i] < level[next_i]) {
                        int pushed_flow = dfs(next_i, std::min(capacity, arc->get_capacity(cur_i)));
                        if(pushed_flow > 0) {
                            arc->add_flow(cur_i, pushed_flow);
                            return pushed_flow;
                        }
                    }
                }
                return 0;
            };
            int pushed_flow;
            do {
                pushed_flow = dfs(source_i, std::numeric_limits<int>::max());
                result += pushed_flow;
            } while(pushed_flow > 0);
        }
    }
};


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