#include<vector>
#include<deque>
#include<algorithm>

class BridgesGraph {
    struct Edge {  // Bidirectional edge
        int u;
        int v;
        
        int get_from(int from_node) {
            if(from_node == u) {
                return v;
            }
            return u;
        }
    };
    struct Node {
        int depth_ = 0;  // Depth of the node in the spanning forest
        int upper_depth_reached_ = 0;  // The maximum depth that can be reached from this node's spanning forest subtree
        bool explored_ = false;
        
        int index;
        std::vector<Edge*> edges;
    };
    
    std::deque<Edge> edges_;  // We use deque to prevent pointer invalidation when exceeding capacity
    std::vector<Node> nodes_;
    
    int _bridges_count_;
    
    void _find_bridges_dfs(Node* node, Edge* last_edge_used = NULL) {
        node->explored_ = true;
        node->upper_depth_reached_ = node->depth_;
        
        for(Edge* edge : node->edges) if(edge != last_edge_used) {  // Go through all edges expect the one from parent
            Node* next = &nodes_[edge->get_from(node->index)];
            if(!next->explored_) {  // Next node not explored, so this edge belongs to the spanning forest
                next->depth_ = node->depth_+1;
                _find_bridges_dfs(next, edge);
                
                node->upper_depth_reached_ = std::min(node->upper_depth_reached_, next->upper_depth_reached_);
                if(next->upper_depth_reached_ == next->depth_) {
                    // Subtree has no edges going up, so this edge is a bridge
                    _bridges_count_++;
                }
            } else {  // Node is explored, so this edge links to subtree or to nodes up the spanning tree
                node->upper_depth_reached_ = std::min(node->upper_depth_reached_, next->depth_);
            }
        }
    }
    
    
public:
    BridgesGraph(int num_nodes) {
        nodes_.resize(num_nodes);
        for(int i=0; i<num_nodes; i++) {
            nodes_[i].index = i;
        }
    }
    
    void add_edge(int u, int v) {
        edges_.push_back({u, v});
        Edge* edge = &edges_.back();
        nodes_[u].edges.push_back(edge);
        nodes_[v].edges.push_back(edge);
    }
    
    int count_bridges() {
        for(Node& node : nodes_) {
            node.depth_ = 0;
            node.explored_ = false;
        }
        _bridges_count_ = 0;
        for(Node& node : nodes_) if(!node.explored_) {
            _find_bridges_dfs(&node);
        }
        return _bridges_count_;
    }
};


int main() {
    BridgesGraph graph(6);
    graph.add_edge(0, 1);
    graph.add_edge(0, 2);
    graph.add_edge(1, 2);
    graph.add_edge(2, 3);
    graph.add_edge(3, 4);
    graph.add_edge(4, 5);
    graph.add_edge(3, 5);
    
    int result = graph.count_bridges();
    return 0;
}