"""Undirected graph: bridges (cut edges) and articulation points (iterative Tarjan)."""
from __future__ import annotations


def _normalize(graph):
    from collections import Counter
    counts = Counter()
    for u, nbrs in (graph or {}).items():
        for v in (nbrs or ()):
            counts[frozenset((u, v))] += 1
    edge_list = []
    for e, c in counts.items():
        if c <= 1:
            mult = 1
        elif c % 2 == 0:
            mult = c // 2
        else:
            mult = c
        edge_list.extend([e] * mult)
    # nodes
    nodes = set((graph or {}).keys())
    for e in edge_list:
        for n in e:
            nodes.add(n)
    # build adj with unique edge ids by index
    adj = {n: [] for n in nodes}
    for i, e in enumerate(edge_list):
        els = tuple(e)
        if len(els) == 1:
            a = els[0]
            adj[a].append((a, i))
        else:
            a, b = els
            adj[a].append((b, i))
            adj[b].append((a, i))
    return nodes, adj, edge_list


def analyze(graph):
    nodes, adj, edge_list = _normalize(graph)
    if not nodes:
        return set(), set()

    disc = {}
    low = {}
    timer = [0]
    bridges = set()
    art = set()
    children_root = {}

    for start in sorted(nodes, key=lambda x: (type(x).__name__, repr(x))):
        if start in disc:
            continue
        root = start
        children_root[root] = 0
        disc[root] = low[root] = timer[0]
        timer[0] += 1
        stack = [root]
        parent_node = {root: None}
        parent_edge = {root: None}
        frames = {root: 0}  # next child index
        cur = root
        while True:
            if frames[cur] < len(adj[cur]):
                nbr, eid_ = adj[cur][frames[cur]]
                frames[cur] += 1
                if eid_ == parent_edge[cur]:
                    continue
                if nbr not in disc:
                    parent_node[nbr] = cur
                    parent_edge[nbr] = eid_
                    disc[nbr] = low[nbr] = timer[0]
                    timer[0] += 1
                    stack.append(nbr)
                    frames[nbr] = 0
                    if cur == root:
                        children_root[root] += 1
                    cur = nbr
                else:
                    if nbr in stack:
                        low[cur] = min(low[cur], disc[nbr])
            else:
                stack.pop()
                if stack:
                    pnode = stack[-1]
                    low[pnode] = min(low[pnode], low[cur])
                    if low[cur] > disc[pnode]:
                        bridges.add(edge_list[parent_edge[cur]])
                    if pnode != root and low[cur] >= disc[pnode]:
                        art.add(pnode)
                del frames[cur]
                if not stack:
                    break
                cur = stack[-1]
        if children_root.get(root, 0) > 1:
            art.add(root)

    return bridges, art


def bridges(graph):
    b, _ = analyze(graph)
    return b


def articulation_points(graph):
    _, a = analyze(graph)
    return a