"""
p70 — Reconstruct Itinerary (LeetCode 332, HARD).

Find an Eulerian path starting at "JFK" in a directed multigraph of tickets,
returning the lexicographically smallest valid itinerary.

Algorithm: Hierholzer's algorithm with min-heap of destinations.
Key insight: append nodes in POST-ORDER during DFS, then reverse.
This handles the "dead-end" subgraph correctly (greedy pre-order DFS fails).
"""
from __future__ import annotations
import heapq
import random
from collections import defaultdict
from itertools import permutations
from typing import List


def find_itinerary_hierholzer(tickets: List[List[str]]) -> List[str]:
    """Recursive Hierholzer with min-heap of destinations."""
    graph = defaultdict(list)
    for src, dst in tickets:
        heapq.heappush(graph[src], dst)

    route: List[str] = []

    def dfs(u: str) -> None:
        # INVARIANT: pop edges in lex order; recurse before appending (post-order).
        while graph[u]:
            v = heapq.heappop(graph[u])
            dfs(v)
        route.append(u)

    dfs("JFK")
    return route[::-1]


def find_itinerary_iterative(tickets: List[List[str]]) -> List[str]:
    """Iterative Hierholzer — production form."""
    graph = defaultdict(list)
    for src, dst in tickets:
        heapq.heappush(graph[src], dst)

    stack = ["JFK"]
    route: List[str] = []
    while stack:
        u = stack[-1]
        if graph[u]:
            v = heapq.heappop(graph[u])
            stack.append(v)
        else:
            route.append(stack.pop())
    return route[::-1]


def find_itinerary_brute(tickets: List[List[str]]) -> List[str]:
    """Try all permutations; among valid Eulerian paths from JFK, return lex-smallest."""
    n = len(tickets)
    best: List[str] = []
    # Sort permutations of INDICES; the resulting itinerary lex-ordering depends on path
    # so we enumerate all and pick lex-smallest itinerary.
    for perm in permutations(range(n)):
        path = ["JFK"]
        ok = True
        for idx in perm:
            src, dst = tickets[idx]
            if path[-1] != src:
                ok = False
                break
            path.append(dst)
        if ok:
            if not best or path < best:
                best = path
    return best


def edge_cases() -> None:
    t1 = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
    assert find_itinerary_hierholzer(t1) == ["JFK", "MUC", "LHR", "SFO", "SJC"]

    t2 = [["JFK", "SFO"], ["JFK", "ATL"], ["SFO", "ATL"], ["ATL", "JFK"], ["ATL", "SFO"]]
    assert find_itinerary_hierholzer(t2) == ["JFK", "ATL", "JFK", "SFO", "ATL", "SFO"]
    assert find_itinerary_iterative(t2) == ["JFK", "ATL", "JFK", "SFO", "ATL", "SFO"]

    # Single ticket
    assert find_itinerary_hierholzer([["JFK", "AAA"]]) == ["JFK", "AAA"]

    # Loop
    assert find_itinerary_hierholzer([["JFK", "A"], ["A", "JFK"]]) == ["JFK", "A", "JFK"]
    print("edge_cases: PASS")


def _random_eulerian_tickets(rng: random.Random) -> List[List[str]]:
    """Build a random Eulerian path starting from JFK."""
    n_steps = rng.randint(1, 5)
    cities = ["JFK", "AAA", "BBB", "CCC"]
    current = "JFK"
    tickets = []
    for _ in range(n_steps):
        nxt = rng.choice(cities)
        tickets.append([current, nxt])
        current = nxt
    rng.shuffle(tickets)
    return tickets


def stress_test() -> None:
    rng = random.Random(42)
    for trial in range(150):
        tickets = _random_eulerian_tickets(rng)
        a = find_itinerary_hierholzer([t[:] for t in tickets])
        b = find_itinerary_iterative([t[:] for t in tickets])
        c = find_itinerary_brute([t[:] for t in tickets])
        assert a == b == c, f"trial {trial}: tickets={tickets} hier={a} iter={b} brute={c}"
    print("stress_test: 150 trials — recursive Hierholzer, iterative Hierholzer, brute permutation all produce identical lex-smallest itinerary.")


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