"""
p62 — Course Schedule II (LeetCode 210, MEDIUM).

Topological sort. Two algorithms: Kahn (BFS w/ indegree) and DFS post-order.
Edge convention: prerequisites[i] = [a, b] => b must come before a => edge b -> a.
"""
from __future__ import annotations
import random
from collections import deque
from itertools import permutations
from typing import List


def find_order_kahn(num_courses: int, prerequisites: List[List[int]]) -> List[int]:
    adj: List[List[int]] = [[] for _ in range(num_courses)]
    indeg = [0] * num_courses
    for a, b in prerequisites:
        adj[b].append(a)
        indeg[a] += 1
    q = deque(v for v in range(num_courses) if indeg[v] == 0)
    result: List[int] = []
    while q:
        v = q.popleft()
        result.append(v)
        for u in adj[v]:
            indeg[u] -= 1
            if indeg[u] == 0:
                q.append(u)
    return result if len(result) == num_courses else []


WHITE, GRAY, BLACK = 0, 1, 2


def find_order_dfs(num_courses: int, prerequisites: List[List[int]]) -> List[int]:
    adj: List[List[int]] = [[] for _ in range(num_courses)]
    for a, b in prerequisites:
        adj[b].append(a)
    color = [WHITE] * num_courses
    order: List[int] = []
    has_cycle = False

    def dfs(v: int) -> None:
        nonlocal has_cycle
        # Iterative DFS to avoid recursion limit on large inputs.
        stack: List[tuple] = [(v, iter(adj[v]))]
        color[v] = GRAY
        while stack:
            node, it = stack[-1]
            nxt = next(it, None)
            if nxt is None:
                color[node] = BLACK
                order.append(node)
                stack.pop()
            else:
                if color[nxt] == GRAY:
                    has_cycle = True
                    return
                if color[nxt] == WHITE:
                    color[nxt] = GRAY
                    stack.append((nxt, iter(adj[nxt])))

    for v in range(num_courses):
        if color[v] == WHITE:
            dfs(v)
            if has_cycle:
                return []
    order.reverse()
    return order


def _is_valid_topo(order: List[int], n: int, prereqs: List[List[int]]) -> bool:
    if len(order) != n or set(order) != set(range(n)):
        return False
    pos = {v: i for i, v in enumerate(order)}
    for a, b in prereqs:
        if pos[b] >= pos[a]:
            return False
    return True


def find_order_brute(num_courses: int, prerequisites: List[List[int]]) -> List[int]:
    for perm in permutations(range(num_courses)):
        if _is_valid_topo(list(perm), num_courses, prerequisites):
            return list(perm)
    return []


def edge_cases() -> None:
    o = find_order_kahn(2, [[1, 0]])
    assert _is_valid_topo(o, 2, [[1, 0]])
    o = find_order_dfs(2, [[1, 0]])
    assert _is_valid_topo(o, 2, [[1, 0]])
    o = find_order_kahn(4, [[1, 0], [2, 0], [3, 1], [3, 2]])
    assert _is_valid_topo(o, 4, [[1, 0], [2, 0], [3, 1], [3, 2]])
    assert find_order_kahn(2, [[1, 0], [0, 1]]) == []   # cycle
    assert find_order_dfs(2, [[1, 0], [0, 1]]) == []
    assert find_order_kahn(1, [[0, 0]]) == []           # self-loop
    assert find_order_dfs(1, [[0, 0]]) == []
    o = find_order_kahn(3, [])
    assert _is_valid_topo(o, 3, [])
    o = find_order_dfs(5, [])
    assert _is_valid_topo(o, 5, [])
    print("edge_cases: PASS")


def stress_test() -> None:
    rng = random.Random(42)
    for trial in range(500):
        n = rng.randint(1, 6)
        # Generate random edges; could create cycles.
        m = rng.randint(0, n * (n - 1) // 2 + 1)
        prereqs = []
        for _ in range(m):
            a = rng.randrange(n)
            b = rng.randrange(n)
            if a != b:
                prereqs.append([a, b])
        kahn = find_order_kahn(n, prereqs)
        dfs = find_order_dfs(n, prereqs)
        brute = find_order_brute(n, prereqs)
        # All three: either all return a valid topo, or all return [] (cycle).
        kahn_ok = (kahn != []) or (n == 0)
        dfs_ok = (dfs != []) or (n == 0)
        brute_ok = (brute != []) or (n == 0)
        # Cycle existence is unambiguous; agreement on whether result is empty.
        kahn_has = (len(kahn) == n)
        dfs_has = (len(dfs) == n)
        brute_has = (len(brute) == n)
        assert kahn_has == dfs_has == brute_has, (
            f"trial {trial}: n={n} prereqs={prereqs} kahn={kahn} dfs={dfs} brute={brute}"
        )
        if kahn_has:
            assert _is_valid_topo(kahn, n, prereqs)
            assert _is_valid_topo(dfs, n, prereqs)
            assert _is_valid_topo(brute, n, prereqs)
    print("stress_test: 500 trials — Kahn, DFS, brute all agree on feasibility and yield valid topos.")


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