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

    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        this.n = n;
        adj = new ArrayList[n];

        for (int i = 0; i < n; i++) adj[i] = new ArrayList<Integer>();

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

        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 (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 if (next != parent) {
                minConnected[node] = Math.min(minConnected[node], dfsOrder[next]);
            }
        }
    }
}