"""
LC 133 — Clone Graph.

Two implementations:
    1. clone_graph_dfs — recursive memoized DFS (canonical).
    2. clone_graph_bfs — iterative deque-based BFS (same memo, safer for deep graphs).

Test infrastructure:
    - serialize(node) -> adjacency list keyed by integer ids.
    - deserialize(adj) -> Node head (node with id 0).
    - graphs_isomorphic_and_independent(old, new) -> bool.

INVARIANT (both clones): for every old node O, memo[O] is the unique New node
                         such that mutating New.neighbors does not affect O.neighbors.
INVARIANT: memo[old] is written BEFORE recursing/enqueueing old's neighbors.
"""

from __future__ import annotations

import random
import sys
from collections import deque

sys.setrecursionlimit(20_000)


class Node:
    __slots__ = ("val", "neighbors")

    def __init__(self, val: int = 0, neighbors: list[Node] | None = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []


# ----------------------------------------------------------------------
# Solution A — Recursive DFS.
# ----------------------------------------------------------------------

def clone_graph_dfs(node: Node | None) -> Node | None:
    if node is None:
        return None
    memo: dict[int, Node] = {}  # id(old) -> new

    def dfs(old: Node) -> Node:
        key = id(old)
        if key in memo:
            return memo[key]
        new = Node(old.val)
        memo[key] = new  # CRITICAL: register before recursing
        for nb in old.neighbors:
            new.neighbors.append(dfs(nb))
        return new

    return dfs(node)


# ----------------------------------------------------------------------
# Solution B — Iterative BFS.
# ----------------------------------------------------------------------

def clone_graph_bfs(node: Node | None) -> Node | None:
    if node is None:
        return None
    memo: dict[int, Node] = {id(node): Node(node.val)}
    q: deque[Node] = deque([node])
    while q:
        old = q.popleft()
        new = memo[id(old)]
        for nb in old.neighbors:
            if id(nb) not in memo:
                memo[id(nb)] = Node(nb.val)
                q.append(nb)
            new.neighbors.append(memo[id(nb)])
    return memo[id(node)]


# ----------------------------------------------------------------------
# Test infrastructure.
# ----------------------------------------------------------------------

def serialize(node: Node | None) -> list[list[int]]:
    """Adjacency list keyed by BFS-discovery order. Head is id 0."""
    if node is None:
        return []
    ids: dict[int, int] = {id(node): 0}
    order: list[Node] = [node]
    q: deque[Node] = deque([node])
    while q:
        cur = q.popleft()
        for nb in cur.neighbors:
            if id(nb) not in ids:
                ids[id(nb)] = len(order)
                order.append(nb)
                q.append(nb)
    return [[ids[id(nb)] for nb in n.neighbors] for n in order]


def deserialize(adj: list[list[int]]) -> Node | None:
    if not adj:
        return None
    nodes = [Node(i + 1) for i in range(len(adj))]  # vals 1..N like LC convention
    for i, neighs in enumerate(adj):
        nodes[i].neighbors = [nodes[j] for j in neighs]
    return nodes[0]


def graphs_isomorphic_and_independent(old: Node | None, new: Node | None) -> bool:
    """Check (1) structural isomorphism via adjacency-list compare; (2) no shared
    node objects; (3) mutating new does not change old."""
    if old is None and new is None:
        return True
    if old is None or new is None:
        return False

    old_adj = serialize(old)
    new_adj = serialize(new)
    if old_adj != new_adj:
        return False

    # No shared node objects.
    old_ids: set[int] = set()
    q: deque[Node] = deque([old])
    seen: set[int] = {id(old)}
    while q:
        n = q.popleft()
        old_ids.add(id(n))
        for nb in n.neighbors:
            if id(nb) not in seen:
                seen.add(id(nb))
                q.append(nb)

    q = deque([new])
    seen = {id(new)}
    while q:
        n = q.popleft()
        if id(n) in old_ids:
            return False  # shared object!
        for nb in n.neighbors:
            if id(nb) not in seen:
                seen.add(id(nb))
                q.append(nb)

    # Mutation test: clear all new.neighbors, confirm old.neighbors still match old_adj.
    new_nodes: list[Node] = []
    q = deque([new])
    seen = {id(new)}
    while q:
        n = q.popleft()
        new_nodes.append(n)
        for nb in n.neighbors:
            if id(nb) not in seen:
                seen.add(id(nb))
                q.append(nb)
    for n in new_nodes:
        n.neighbors.clear()

    if serialize(old) != old_adj:
        return False
    return True


# ----------------------------------------------------------------------
# Random graph generation.
# ----------------------------------------------------------------------

def random_connected_undirected_graph(rng: random.Random, n: int, edge_prob: float) -> Node | None:
    if n == 0:
        return None
    nodes = [Node(i + 1) for i in range(n)]
    # Spanning tree first (guarantees connectivity).
    for i in range(1, n):
        j = rng.randint(0, i - 1)
        nodes[i].neighbors.append(nodes[j])
        nodes[j].neighbors.append(nodes[i])
    # Extra edges (avoid self-loops & duplicates).
    existing: set[tuple[int, int]] = set()
    for i in range(n):
        for nb in nodes[i].neighbors:
            existing.add((i, nb.val - 1))
    for i in range(n):
        for j in range(i + 1, n):
            if (i, j) not in existing and rng.random() < edge_prob:
                nodes[i].neighbors.append(nodes[j])
                nodes[j].neighbors.append(nodes[i])
    return nodes[0]


# ----------------------------------------------------------------------
# Stress test.
# ----------------------------------------------------------------------

def stress_test() -> None:
    rng = random.Random(42)
    n_iter = 1000
    for _ in range(n_iter):
        n = rng.randint(1, 15)
        head = random_connected_undirected_graph(rng, n, rng.uniform(0.1, 0.5))

        # Build a snapshot we can compare against after each clone test.
        orig_snapshot = serialize(head)

        for cloner in (clone_graph_dfs, clone_graph_bfs):
            cloned = cloner(head)
            assert graphs_isomorphic_and_independent(head, cloned), (
                f"{cloner.__name__} failed isomorphism/independence on n={n}"
            )
            # Re-verify original is intact after the mutation test.
            assert serialize(head) == orig_snapshot, (
                f"{cloner.__name__} corrupted original after mutation test"
            )
    print(f"stress_test: {n_iter} random connected graphs — DFS & BFS clones isomorphic, "
          "independent, original intact.")


# ----------------------------------------------------------------------
# Edge cases.
# ----------------------------------------------------------------------

def edge_cases() -> None:
    # None input.
    assert clone_graph_dfs(None) is None
    assert clone_graph_bfs(None) is None

    # Single isolated node.
    n = Node(1)
    for cloner in (clone_graph_dfs, clone_graph_bfs):
        c = cloner(n)
        assert c is not None
        assert c.val == 1
        assert c.neighbors == []
        assert c is not n

    # Single node with self-loop.
    n = Node(1)
    n.neighbors = [n]
    for cloner in (clone_graph_dfs, clone_graph_bfs):
        c = cloner(n)
        assert c is not None and c is not n
        assert len(c.neighbors) == 1
        assert c.neighbors[0] is c  # self-loop preserved in clone
        assert c.neighbors[0] is not n

    # 2-node cycle (LC canonical small).
    a, b = Node(1), Node(2)
    a.neighbors = [b]
    b.neighbors = [a]
    for cloner in (clone_graph_dfs, clone_graph_bfs):
        c = cloner(a)
        assert c is not None and c is not a
        assert len(c.neighbors) == 1
        c2 = c.neighbors[0]
        assert c2.val == 2 and c2 is not b
        assert len(c2.neighbors) == 1
        assert c2.neighbors[0] is c  # back-edge to clone, not original

    # K4 (complete graph on 4 nodes).
    nodes = [Node(i + 1) for i in range(4)]
    for i in range(4):
        for j in range(4):
            if i != j:
                nodes[i].neighbors.append(nodes[j])
    snap = serialize(nodes[0])
    for cloner in (clone_graph_dfs, clone_graph_bfs):
        c = cloner(nodes[0])
        assert graphs_isomorphic_and_independent(nodes[0], c)
        assert serialize(nodes[0]) == snap

    # Line graph 1-2-3-4-5.
    line = [Node(i + 1) for i in range(5)]
    for i in range(4):
        line[i].neighbors.append(line[i + 1])
        line[i + 1].neighbors.append(line[i])
    snap = serialize(line[0])
    for cloner in (clone_graph_dfs, clone_graph_bfs):
        c = cloner(line[0])
        assert graphs_isomorphic_and_independent(line[0], c)
        assert serialize(line[0]) == snap

    # Duplicate values (algorithm must not rely on val uniqueness).
    x, y = Node(7), Node(7)
    x.neighbors = [y]
    y.neighbors = [x]
    for cloner in (clone_graph_dfs, clone_graph_bfs):
        c = cloner(x)
        assert c is not None and c is not x
        assert c.val == 7
        assert len(c.neighbors) == 1
        c2 = c.neighbors[0]
        assert c2.val == 7 and c2 is not y and c2 is not x
        assert c2.neighbors[0] is c

    print("edge_cases: PASS")


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