"""
LC 207 — Course Schedule (cycle detection on directed graph).

Implementations:
    1. can_finish_kahns         — BFS topological sort (Kahn's). Returns bool.
    2. can_finish_dfs_coloring  — 3-color DFS. Returns bool.
    3. find_order_kahns         — LC 210 bonus. Returns ordering or [].
    4. find_cycle_dfs           — Bonus. Returns one cycle (as list) or None.
    5. has_cycle_brute          — Oracle. O(N(V+E)). DFS from each node, parent path.

INVARIANT (Kahn's): `processed == N` at end iff no cycle.
INVARIANT (3-color): GRAY = currently on recursion stack. Encountering GRAY = cycle.
EDGE DIRECTION: [a, b] means "b is prerequisite of a" → edge b → a in adj list.
"""

from __future__ import annotations

import random
import sys
from collections import deque

sys.setrecursionlimit(20_000)


# ----------------------------------------------------------------------
# Solution A — Kahn's algorithm.
# ----------------------------------------------------------------------

def can_finish_kahns(N: int, prereqs: list[list[int]]) -> bool:
    adj: list[list[int]] = [[] for _ in range(N)]
    indeg: list[int] = [0] * N
    for a, b in prereqs:
        adj[b].append(a)
        indeg[a] += 1
    q: deque[int] = deque(i for i in range(N) if indeg[i] == 0)
    processed = 0
    while q:
        u = q.popleft()
        processed += 1
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return processed == N


# ----------------------------------------------------------------------
# Solution B — DFS with 3-coloring.
# ----------------------------------------------------------------------

WHITE, GRAY, BLACK = 0, 1, 2


def can_finish_dfs_coloring(N: int, prereqs: list[list[int]]) -> bool:
    adj: list[list[int]] = [[] for _ in range(N)]
    for a, b in prereqs:
        adj[b].append(a)
    color: list[int] = [WHITE] * N

    def dfs(u: int) -> bool:
        # Returns True if subgraph rooted at u is cycle-free.
        color[u] = GRAY
        for v in adj[u]:
            if color[v] == GRAY:
                return False  # back-edge
            if color[v] == WHITE and not dfs(v):
                return False
        color[u] = BLACK
        return True

    for i in range(N):
        if color[i] == WHITE and not dfs(i):
            return False
    return True


# ----------------------------------------------------------------------
# Solution C — LC 210: return the topological order.
# ----------------------------------------------------------------------

def find_order_kahns(N: int, prereqs: list[list[int]]) -> list[int]:
    adj: list[list[int]] = [[] for _ in range(N)]
    indeg: list[int] = [0] * N
    for a, b in prereqs:
        adj[b].append(a)
        indeg[a] += 1
    q: deque[int] = deque(i for i in range(N) if indeg[i] == 0)
    order: list[int] = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == N else []


# ----------------------------------------------------------------------
# Solution D — return a witnessing cycle (or None).
# ----------------------------------------------------------------------

def find_cycle_dfs(N: int, prereqs: list[list[int]]) -> list[int] | None:
    adj: list[list[int]] = [[] for _ in range(N)]
    for a, b in prereqs:
        adj[b].append(a)
    color: list[int] = [WHITE] * N
    parent: list[int] = [-1] * N
    cycle_found: list[list[int]] = []  # holds at most one cycle, as a list to allow mutation in nested

    def dfs(u: int) -> bool:
        color[u] = GRAY
        for v in adj[u]:
            if color[v] == GRAY:
                # Walk parent pointers from u back to v to build the cycle.
                cyc = [v, u]
                w = u
                while parent[w] != -1 and w != v:
                    w = parent[w]
                    cyc.append(w)
                    if w == v:
                        break
                cyc.reverse()
                cycle_found.append(cyc)
                return False
            if color[v] == WHITE:
                parent[v] = u
                if not dfs(v):
                    return False
        color[u] = BLACK
        return True

    for i in range(N):
        if color[i] == WHITE and not dfs(i):
            return cycle_found[0]
    return None


# ----------------------------------------------------------------------
# Solution E — Brute oracle. O(N(V+E)).
# ----------------------------------------------------------------------

def has_cycle_brute(N: int, prereqs: list[list[int]]) -> bool:
    adj: list[list[int]] = [[] for _ in range(N)]
    for a, b in prereqs:
        adj[b].append(a)

    # DFS from each start node, tracking nodes on current path.
    def dfs(u: int, on_path: set[int], visited: set[int]) -> bool:
        if u in on_path:
            return True
        if u in visited:
            return False
        on_path.add(u)
        for v in adj[u]:
            if dfs(v, on_path, visited):
                return True
        on_path.remove(u)
        visited.add(u)
        return False

    visited: set[int] = set()
    for i in range(N):
        if i not in visited:
            if dfs(i, set(), visited):
                return True
    return False


# ----------------------------------------------------------------------
# Helpers.
# ----------------------------------------------------------------------

def random_dag(rng: random.Random, n: int, edge_prob: float) -> list[list[int]]:
    """Random DAG: pick a random topo order, only allow edges in increasing direction."""
    order = list(range(n))
    rng.shuffle(order)
    pos = {node: i for i, node in enumerate(order)}
    prereqs: list[list[int]] = []
    for u in range(n):
        for v in range(n):
            if u != v and pos[u] < pos[v] and rng.random() < edge_prob:
                # u must be done before v → [v, u]
                prereqs.append([v, u])
    return prereqs


def random_graph(rng: random.Random, n: int, edge_prob: float) -> list[list[int]]:
    """Random directed graph (may have cycles)."""
    prereqs: list[list[int]] = []
    for u in range(n):
        for v in range(n):
            if u != v and rng.random() < edge_prob:
                prereqs.append([u, v])
    return prereqs


def verify_topo_order(N: int, prereqs: list[list[int]], order: list[int]) -> bool:
    if len(order) != N:
        return False
    pos = {node: i for i, node in enumerate(order)}
    for a, b in prereqs:
        if pos[b] >= pos[a]:
            return False
    return True


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

def stress_test() -> None:
    rng = random.Random(42)
    n_iter = 500

    # Pass 1: random DAGs (always acyclic).
    for _ in range(n_iter):
        n = rng.randint(1, 12)
        prereqs = random_dag(rng, n, rng.uniform(0.05, 0.4))
        expected = has_cycle_brute(n, prereqs)
        assert not expected, f"random_dag generated a cyclic graph?! n={n} prereqs={prereqs}"
        assert can_finish_kahns(n, prereqs)
        assert can_finish_dfs_coloring(n, prereqs)
        order = find_order_kahns(n, prereqs)
        assert verify_topo_order(n, prereqs, order), f"Bad order on DAG n={n}"
        assert find_cycle_dfs(n, prereqs) is None

    # Pass 2: random possibly-cyclic graphs.
    for _ in range(n_iter):
        n = rng.randint(1, 10)
        prereqs = random_graph(rng, n, rng.uniform(0.1, 0.5))
        expected_has_cycle = has_cycle_brute(n, prereqs)
        a = can_finish_kahns(n, prereqs)
        b = can_finish_dfs_coloring(n, prereqs)
        assert a == b == (not expected_has_cycle), (
            f"Disagreement: kahns={a} dfs={b} brute_has_cycle={expected_has_cycle}\n"
            f"n={n} prereqs={prereqs}"
        )
        order = find_order_kahns(n, prereqs)
        if expected_has_cycle:
            assert order == [], f"Cycle but order returned: {order}"
            assert find_cycle_dfs(n, prereqs) is not None
        else:
            assert verify_topo_order(n, prereqs, order)
            assert find_cycle_dfs(n, prereqs) is None

    print(f"stress_test: {2 * n_iter} random graphs — Kahn's, 3-color DFS, find_order, "
          "find_cycle all agree with brute oracle.")


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

def edge_cases() -> None:
    # Empty prereqs.
    assert can_finish_kahns(0, []) is True
    assert can_finish_kahns(3, []) is True
    assert can_finish_dfs_coloring(0, []) is True
    assert can_finish_dfs_coloring(3, []) is True
    assert find_order_kahns(3, []) == [0, 1, 2]
    assert find_cycle_dfs(3, []) is None

    # Self-loop.
    assert can_finish_kahns(1, [[0, 0]]) is False
    assert can_finish_dfs_coloring(1, [[0, 0]]) is False
    assert find_order_kahns(1, [[0, 0]]) == []
    cyc = find_cycle_dfs(1, [[0, 0]])
    assert cyc is not None and cyc[0] == cyc[-1] == 0

    # Two-node cycle.
    assert can_finish_kahns(2, [[1, 0], [0, 1]]) is False
    assert can_finish_dfs_coloring(2, [[1, 0], [0, 1]]) is False

    # LC canonical: N=2, [[1,0]] → True.
    assert can_finish_kahns(2, [[1, 0]]) is True
    assert can_finish_dfs_coloring(2, [[1, 0]]) is True
    o = find_order_kahns(2, [[1, 0]])
    assert verify_topo_order(2, [[1, 0]], o)

    # Long chain (1000 nodes). Tests recursion limit.
    n = 1000
    chain = [[i + 1, i] for i in range(n - 1)]
    assert can_finish_kahns(n, chain) is True
    assert can_finish_dfs_coloring(n, chain) is True
    o = find_order_kahns(n, chain)
    assert verify_topo_order(n, chain, o)

    # Diamond.
    diamond = [[1, 0], [2, 0], [3, 1], [3, 2]]
    assert can_finish_kahns(4, diamond) is True
    assert can_finish_dfs_coloring(4, diamond) is True
    o = find_order_kahns(4, diamond)
    assert verify_topo_order(4, diamond, o)

    # Disconnected: one valid + one cyclic.
    mixed = [[1, 0], [3, 2], [2, 3]]  # 0->1 fine; 2<->3 cycle
    assert can_finish_kahns(4, mixed) is False
    assert can_finish_dfs_coloring(4, mixed) is False
    assert find_order_kahns(4, mixed) == []

    print("edge_cases: PASS")


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