class Solution {
    vector<int> status;
    vector<int> visOrder;
    vector<int> reach; // reach[i]: farthest ancestor that i can reach in dfs tree
    vector<vector<int>> graph;
    int seqCount;

    int dfs(int node, int parent) {
        visOrder[node] = seqCount ++;
        status[node] = 1;
        int ancestor = node;
        for (auto next : graph[node]) {
            if (next == parent)
                continue;
            int tmp = next;
            if (status[tmp] == 0) {
                tmp = dfs(tmp, node);
            }
            if (visOrder[tmp] <= visOrder[ancestor]) {
                ancestor = tmp;
            }
        }
        //status[node] = 2;
        reach[node] = ancestor;
        return ancestor;
    }
    void init(int n, vector<vector<int>>& connections) {
        status.resize(n, 0);
        visOrder.resize(n, INT_MAX);
        reach.resize(n);
        seqCount = 0;
        graph.resize(n);
        for (auto & conn : connections) {
            graph[conn[0]].push_back(conn[1]);
            graph[conn[1]].push_back(conn[0]);
        }
    }
public:
    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
        init(n, connections);
        dfs(0, -1);
        vector<vector<int>> res;
        for (auto & conn: connections) {
            if (visOrder[conn[0]] < visOrder[conn[1]] && visOrder[reach[conn[1]]] < visOrder[conn[1]])
                continue;
            if (visOrder[conn[1]] < visOrder[conn[0]] && visOrder[reach[conn[0]]] < visOrder[conn[0]])
                continue;
            res.push_back(conn);
        }
        return res;
    }
};