// Runtime: 92 ms, faster than 97.49% of Java online submissions for Critical Connections in a Network.
// Memory Usage: 121.2 MB, less than 100.00% of Java online submissions for Critical Connections in a Network.
class Solution {
    List<Integer>[] adj;
    int[] dfsOrder;
    int lastNodeOrder;
    int[] minConnected;
    List<List<Integer>> result;

    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        adj = new ArrayList[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<Integer>();

        for (List<Integer> conn: connections) {
            int from = conn.get(0);
            int to = conn.get(1);
            adj[from].add(to);
            adj[to].add(from);
        }

        dfsOrder = new int[n];
        minConnected = new int[n];

        result = new ArrayList<>();

        for (int node = 0; node < n; node++)
            if (dfsOrder[node] == 0) dfs(node, -1);

        return result;
    }

    private void dfs(int node, int parent) {
        dfsOrder[node] = ++lastNodeOrder;
        minConnected[node] = dfsOrder[node];

        for (int next: adj[node]) {
            if (next == parent) continue;

            if (dfsOrder[next] == 0) {
                dfs(next, node);
                minConnected[node] = Math.min(minConnected[node], minConnected[next]);
                if (minConnected[next] == dfsOrder[next]) {
                    result.add(Arrays.asList(node, next));
                    continue;
                }
            } else minConnected[node] = Math.min(minConnected[node], dfsOrder[next]);
        }
    }
}