"""
p68 — Critical Connections in a Network (LeetCode 1192, HARD).

Tarjan's bridge-finding algorithm:
- disc[u] = DFS discovery time of u.
- low[u]  = lowest disc reachable from u's subtree via tree edges + ONE back edge.
- Edge (u, v) where v is u's DFS child is a BRIDGE iff low[v] > disc[u].

LC constraints require iterative DFS (n up to 1e5 -> Python recursion limit).
"""
from __future__ import annotations
import random
import sys
from typing import List


def critical_connections_tarjan(n: int, connections: List[List[int]]) -> List[List[int]]:
    adj: List[List[tuple]] = [[] for _ in range(n)]
    for eid, (u, v) in enumerate(connections):
        adj[u].append((v, eid))
        adj[v].append((u, eid))

    disc = [-1] * n
    low = [0] * n
    timer = 0
    bridges: List[List[int]] = []

    for start in range(n):
        if disc[start] != -1:
            continue
        disc[start] = timer
        low[start] = timer
        timer += 1
        # INVARIANT stack frames: (u, parent_edge_id, iterator over adj[u]).
        # Parent_edge_id is what we DON'T traverse back along (skips the tree edge that brought us).
        stack = [(start, -1, iter(adj[start]))]
        while stack:
            u, p_eid, it = stack[-1]
            descended = False
            for v, eid in it:
                if eid == p_eid:
                    continue   # don't bounce back along the SAME edge (handles multi-edges correctly)
                if disc[v] != -1:
                    # back edge to ancestor v: use disc[v] (NOT low[v]) per Tarjan's rule
                    if disc[v] < low[u]:
                        low[u] = disc[v]
                else:
                    # tree edge: descend
                    disc[v] = timer
                    low[v] = timer
                    timer += 1
                    stack.append((v, eid, iter(adj[v])))
                    descended = True
                    break
            if not descended:
                # done with u — pop and propagate to parent
                stack.pop()
                if stack:
                    parent_u = stack[-1][0]
                    if low[u] < low[parent_u]:
                        low[parent_u] = low[u]
                    if low[u] > disc[parent_u]:
                        bridges.append([parent_u, u])
    return bridges


def critical_connections_tarjan_recursive(n: int, connections: List[List[int]]) -> List[List[int]]:
    adj: List[List[tuple]] = [[] for _ in range(n)]
    for eid, (u, v) in enumerate(connections):
        adj[u].append((v, eid))
        adj[v].append((u, eid))

    disc = [-1] * n
    low = [0] * n
    bridges: List[List[int]] = []
    timer = [0]

    sys.setrecursionlimit(max(10000, n * 4))

    def dfs(u: int, p_eid: int) -> None:
        disc[u] = timer[0]
        low[u] = timer[0]
        timer[0] += 1
        for v, eid in adj[u]:
            if eid == p_eid:
                continue
            if disc[v] != -1:
                if disc[v] < low[u]:
                    low[u] = disc[v]
            else:
                dfs(v, eid)
                if low[v] < low[u]:
                    low[u] = low[v]
                if low[v] > disc[u]:
                    bridges.append([u, v])

    for start in range(n):
        if disc[start] == -1:
            dfs(start, -1)
    return bridges


def _is_connected_excluding(n: int, connections: List[List[int]], exclude_idx: int) -> bool:
    if n == 0:
        return True
    adj: List[List[int]] = [[] for _ in range(n)]
    for i, (u, v) in enumerate(connections):
        if i == exclude_idx:
            continue
        adj[u].append(v)
        adj[v].append(u)
    seen = [False] * n
    stack = [0]
    seen[0] = True
    count = 1
    while stack:
        u = stack.pop()
        for v in adj[u]:
            if not seen[v]:
                seen[v] = True
                count += 1
                stack.append(v)
    return count == n


def critical_connections_brute(n: int, connections: List[List[int]]) -> List[List[int]]:
    # First check graph is connected with all edges (LC promises this).
    bridges: List[List[int]] = []
    for i, (u, v) in enumerate(connections):
        if not _is_connected_excluding(n, connections, i):
            bridges.append([u, v])
    return bridges


def _normalize(edges: List[List[int]]) -> List[tuple]:
    return sorted(tuple(sorted(e)) for e in edges)


def edge_cases() -> None:
    # Triangle + spoke
    g1 = [[0, 1], [1, 2], [2, 0], [1, 3]]
    assert _normalize(critical_connections_tarjan(4, g1)) == [(1, 3)]
    # Tree — every edge is a bridge
    g2 = [[0, 1], [1, 2], [2, 3]]
    assert _normalize(critical_connections_tarjan(4, g2)) == [(0, 1), (1, 2), (2, 3)]
    # Single edge
    assert _normalize(critical_connections_tarjan(2, [[0, 1]])) == [(0, 1)]
    # Single node — no edges
    assert critical_connections_tarjan(1, []) == []
    # Two triangles joined by a bridge
    g3 = [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4], [4, 5], [5, 3]]
    assert _normalize(critical_connections_tarjan(6, g3)) == [(2, 3)]
    print("edge_cases: PASS")


def _random_connected_graph(n: int, rng: random.Random) -> List[List[int]]:
    # Random spanning tree + a few extras
    nodes = list(range(n))
    rng.shuffle(nodes)
    edges: List[List[int]] = []
    seen = set()
    for i in range(1, n):
        u = nodes[i]
        v = nodes[rng.randrange(i)]
        edges.append([u, v])
        seen.add((min(u, v), max(u, v)))
    extras = rng.randint(0, n)
    for _ in range(extras):
        u = rng.randrange(n)
        v = rng.randrange(n)
        if u == v:
            continue
        k = (min(u, v), max(u, v))
        if k in seen:
            continue
        seen.add(k)
        edges.append([u, v])
    return edges


def stress_test() -> None:
    rng = random.Random(42)
    for trial in range(300):
        n = rng.randint(1, 8)
        g = _random_connected_graph(n, rng)
        a = _normalize(critical_connections_tarjan(n, g))
        b = _normalize(critical_connections_tarjan_recursive(n, g))
        c = _normalize(critical_connections_brute(n, g))
        assert a == b == c, f"trial {trial}: n={n} g={g} iter={a} rec={b} brute={c}"
    print("stress_test: 300 trials — iterative Tarjan, recursive Tarjan, brute remove-and-check all agree.")


if __name__ == "__main__":
    edge_cases()
    stress_test()
    print("ALL TESTS PASSED")