def topo_sort_dfs(graph):
        visited = set()
        stack = []

        def dfs(node):
            visited.add(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    dfs(neighbor)
            stack.append(node)

        for node in graph:
            if node not in visited:
                dfs(node)

        return stack[::-1]  # reverse to get correct topological order

    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        
        # DFS Cycle Detection in Directed Graph
        
        # We need the 3 state tracking for directed graphs

        # Graph Representation:
        #   - unique class = node in a directed graph
        #   - directed edge (c1 -> c2):
        #       means c1 class must be taken BEFORE c2 in course order

        # Problem Abstraction:
        #   - Find a valid ordering of classes
        #   - if a cycle exists between classes, no valid ordering exists

        # 3 State Tracking:
        # During DFS, nodes can be in one of three states:
        #   0 = UNVISITED => node has not been explored yet
        #   1 = VISITING => node is currently in the recursion path 
        #                   active on the recursive call stack
        #   2 = PROCESSED => node and all descendants have been fully processed
        #                    and confirmed to contain no cycles

        # Cycle Detection Insight:
        # If we reach a node already marked VISITING (state = 1),
        # it means we returned to a node already in our current DFS path,
        # which forms a cycle.
        
        # Safety Insight:
        # Once a node becomes VISITED (state = 2),
        # we know all paths below it are cycle-free,
        # so we can safely skip reprocessing it.


        # Initialize Graph + In Degree:
        # tc: O(total_classes)
        # sc: O(C), C = number of unique classes

        # graph[c] = set of classes that come after c
        graph = defaultdict(list)

        # State array
        # 0 = unvisited, 1 = visiting, 2 = visited
        visited = [0] * numCourses

        # Build Graph From Adjacent Classes
        # C = number of classes
        # L = average number of pre requisites
        # tc: O(C * L)
        for course, prereq in prerequisites:
            graph[prereq].append(course)


        def dfs(course):

            # Early Prune:
            # We are visiting a node currently in MY OWN recursion path,
            # so cycle exists, course is not possible
            if visited[course] == 1:
                return False

            # Early Return:
            # Already marked as safe, we can skip
            if visited[course] == 2:
                return True

            # Mark node as currently exploring
            visited[course] = 1

            # Explore:
            # Recursively explore all neighbors we are pointing to
            for nei in graph[course]:

                # Neighbor was not processed correctly, thus current node is not safe
                if not dfs(nei):
                    return False
            
            # All nodes after current node have been processed safely,
            # thus current node is also safe
            visited[course] = 2

            # return safely processed
            return True

        # Directed Graph May Be Disconnected:
        # We start DFS from every node to ensure we check all Components:
        # tc: O(V)
        for c in range(numCourses):

            # If class was not safely processed
            if not dfs(c):
                return False

        # All courses processed, no cycles

        # overall: tc O(V + E)
        # overall: sc O(V + E)
        return True

    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        
        # Topological Sort (BFS / Kahn's Algorithm)
        
        # Graph Representation:
        #   - unique class = node in a directed graph
        #   - directed edge (c1 -> c2):
        #       means c1 class must be taken BEFORE c2 in course order

        # Problem Abstraction:
        #   - Find a valid ordering of classes
        #   - if a cycle exists between classes, no valid ordering exists


        # Initialize Graph + In Degree:
        # tc: O(total_classes)
        # sc: O(C), C = number of unique classes

        # graph[c] = set of classes that come after c
        graph = defaultdict(set)

        # in_degree[c] = number of pre requisite classes for c
        indegree = [0] * numCourses

        # Build Graph From Adjacent Classes
        # C = number of classes
        # L = average number of pre requisites
        # tc: O(C * L)
        for course, prereq in prerequisites:

            # Add pre requisite to classes In Degree
            graph[prereq].append(course)

            # Increase In Degree for class
            indegree[course] += 1

        # BFS Topological Sort (Kahn's Algorithm):
        # Add all nodes with an In degree == 0 to the queue

        # Process:
        #   1. Pop node from queue
        #   2. Add to ordering
        #   3. Remove outgoing edges
        #   4. Push new zero in-degree nodes

        # sc: O(V)
        queue = deque()

        # tc: O(V)
        for i in range(numCourses):

            # if node has 0 out degree
            if indegree[i] == 0:
                queue.append(numCourses[i])

        # BFS Topological Sort

        # Tracking classes we have processed, to check for cycles at the end
        count = 0

        # C = nodes (characters)
        # E = edges (ordering constraints)
        # tc: O(C + E)
        while queue:

            # Remove leftmost node with an In Degree of 0
            curr = queue.popleft()

            # Mark node as processed
            count += 1

            # For all directed neighbors of current node,
            # decrease their In Degree by 1
            for nei in graph[curr]:

                # decreasing neighbors In Degree
                indegree[nei] -= 1

                # If neighbor now has an In Degree of 0, 
                # append to stack for processing
                if indegree[nei] == 0:
                    queue.append(nei)

        # If not all nodes were not processed, a cycle exists
        if count != numCourses:
            return False

        # overall: tc O(1)
        # overall: sc O(1)
        return True

    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
            
        # DFS Topological Sort in Directed Graph
        
        # We need the 3 state tracking for directed graphs

        # Graph Representation:
        #   - unique class = node in a directed graph
        #   - directed edge (c1 -> c2):
        #       means c1 class must be taken BEFORE c2 in course order
        #
        # Problem Abstraction:
        #   - Find a valid ordering of classes
        #   - if a cycle exists between classes, no valid ordering exists
        
        # 3 State Tracking:
        # During DFS, nodes can be in one of three states:
        #   0 = UNVISITED => node has not been explored yet
        #   1 = VISITING => node is currently in the recursion path
        #                   active on the recursive call stack
        #   2 = PROCESSED => node and all descendants have been fully processed
        #                    and confirmed to contain no cycles
        
        # Cycle Detection Insight:
        # If we reach a node already marked VISITING (state = 1),
        # it means we returned to a node already in our current DFS path,
        # which forms a cycle.
        
        # Topological Sort Insight:
        # A node is added to the result AFTER all neighbors
        # are processed (postorder traversal).
        # Reversing postorder gives a valid course ordering.

        # Initialize Graph:
        # tc: O(total_classes)
        # sc: O(C), C = number of unique classes

        # graph[c] = classes that come after c
        graph = defaultdict(list)

        # Build Graph From Adjacent Classes
        # C = number of classes
        # L = average number of pre requisites
        # tc: O(C * L)
        for course, prereq in prerequisites:
            graph[prereq].append(course)

        # State array
        # 0 = unvisited, 1 = visiting, 2 = visited
        visited = [0] * numCourses

        # Stores reverse topological order
        res = []

        # Tracks if graph is valid (no cycles)
        is_possible = True

        def dfs(course):
            nonlocal is_possible

            # Early Prune:
            # We are visiting a node currently in MY OWN recursion path,
            # so cycle exists and ordering is not possible
            if visited[course] == 1:
                is_possible = False
                return

            # Early Return:
            # Already safely processed
            if visited[course] == 2:
                return

            # Mark node as currently exploring
            visited[course] = 1

            # Explore:
            # Recursively explore all neighbors
            for nei in graph[course]:

                dfs(nei)

                # Stop early if cycle found
                if not is_possible:
                    return

            # All neighbors processed safely,
            # current node is also safe
            visited[course] = 2

            # Postorder append
            # (reverse topo order)
            res.append(course)

        # Directed Graph May Be Disconnected:
        # We start DFS from every node to ensure we check all Components:
        # tc: O(V)
        for c in range(numCourses):

            # Start DFS from unvisited nodes
            if visited[c] == 0:
                dfs(c)

                # Cycle detected
                if not is_possible:
                    return []

        # Reverse postorder to get correct topological order
        res.reverse()

        # overall: tc O(V + E)
        # overall: sc O(V + E)
        return res

    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        
        # Topological Sort (BFS / Kahn's Algorithm)

        # Graph Representation:
        #   - unique class = node in a directed graph
        #   - directed edge (c1 -> c2):
        #       means c1 class must be taken BEFORE c2 in course order

        # Problem Abstraction:
        #   - Find a valid ordering of classes
        #   - if a cycle exists between classes, no valid ordering exists


        # Initialize Graph + In Degree:
        # tc: O(total_classes)
        # sc: O(C), C = number of unique classes


        # graph[c] = set of classes that come after c
        graph = defaultdict(set)

        # in_degree[c] = number of pre requisite classes for c
        indegree = [0] * numCourses

        # Build Graph From Adjacent Classes
        # C = number of classes
        # L = average number of pre requisites
        # tc: O(C * L)
        for course, prereq in prerequisites:

            # Add pre requisite to classes In Degree
            graph[prereq].append(course)

            # Increase In Degree for class
            indegree[course] += 1

        # BFS Topological Sort (Kahn's Algorithm):
        # Add all nodes with an In degree == 0 to the queue

        # Process:
        #   1. Pop node from queue
        #   2. Add to ordering
        #   3. Remove outgoing edges
        #   4. Push new zero in-degree nodes

        # sc: O(V)
        queue = []

        # tc: O(V)
        for i in range(numCourses):

            # if node has 0 out degree
            if indegree[i] == 0:
                queue.append(numCourses[i])

        # BFS Topological Sort

        # Tracking classes we have processed, to check for cycles at the end
        res = []

        # C = nodes (characters)
        # E = edges (ordering constraints)
        # tc: O(C + E)
        while queue:

            # Remove leftmost node with an In Degree of 0
            curr = queue.popleft()

            # Mark node as processed
            res.append(curr)

            # For all directed neighbors of current node,
            # decrease their In Degree by 1
            for nei in graph[curr]:

                # decreasing neighbors In Degree
                indegree[nei] -= 1

                # If neighbor now has an In Degree of 0, append to stack for processing
                if indegree[nei] == 0:
                    queue.append(nei)

        # If not all nodes were not processed, a cycle exists
        if len(res) != numCourses:
            return []

        # overall: tc O(1)
        # overall: sc O(1)
        return res

    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        
        # DFS Cycle Detection with Connectivity Check (Undirected Graph)

        # We don't need the 3 state tracking for undirected graphs

        # Tree Validation:
        #   1. Must have exactly n-1 edges
        #   2. Must be connected (all nodes reachable from any node)
        #   3. Must not contain cycles
        
        # Edge Case:
        # If edges != n-1, cannot be a tree
        if len(edges) != n - 1:
            return False

        # Initialize Graph:
        # undirected adjacency list

        # tc: O(V + E)
        graph = defaultdict(list)\

        # sc: O(V + E)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        # Track visited nodes
        # tc: O(V)
        visited = set()


        # 
        def dfs(node, parent):

            # Cycle Detection:
            # If we visit a node already seen in this traversal, cycle exists
            if node in visited:
                return False

            # Mark node as visited
            visited.add(node)

            # Explore neighbors
            for nei in graph[node]:

                # Skip back edge to parent
                if nei == parent:
                    continue

                # If neighbor is not safe, current node is not safe
                if not dfs(nei, node):
                    return False
            
            # All neighbors processed safely
            return True

        # Start DFS from node 0
        if not dfs(0, -1):
            return False

        # If not all nodes were not processed, a cycle exists
        if len(visited) != n:
            return False

        # overall: tc O(V + E)
        # overall: sc O(V + E)
        return True

    def validTree(self, n: int, edges: List[List[int]]) -> bool:

        # Topological Sort (BFS / Kahn's Algorithm)

        # Graph Representation:
        #   - node n = node in a undirected graph
        #   - undirected edge (n1 <-> n2)

        # Problem Abstraction:
        #   - validate (n-1) edges
        #   - validate all nodes are connected in tree
        #   - validate no cycles

        # Edge Case:
        # A valid tree for n nodes, it must have(n - 1) edges
        if len(edges) != n - 1:
            return False

        # Initialize Graph + In Degree:
        # tc: O(total_classes)
        # sc: O(C), C = number of unique classes
        
        # graph[c] = node connected to c
        graph = defaultdict(set)

        # Mark nodes as connected
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        # Tracking classes we have processed, to check for cycles at the end
        visited = set()

        # Iterative Queue
        # sc: O(E)
        queue = deque()

        # Build Graph from any node (undirected so order does not matter)
        queue.append((0, -1))

        # While we still have nodes
        # tc: O(V)
        while queue:

            # Remove leftmost node
            node, parent = queue.popleft()

            # Early Exit:
            # node has already been processed, 
            # cycle has been detected
            if node in visited:
                return False

            # Mark node as processed
            visited.add(node)

            # For all directed neighbors of current node,
            # append them for processing
            for nei in graph[node]:

                # ignore if node is pointing to self
                if nei != parent:

                    # append to stack for processing
                    queue.append((nei, node))

        # If not all nodes were not processed, a cycle exists
        if len(visited) != n:
            return False

        # overall: tc O(1)
        # overall: sc O(1)
        return True

    def validTree(self, n: int, edges: List[List[int]]) -> bool:

        # Union-Find (Disjoint Set) for Cycle Detection in Undirected Graph

        # Union Find can be used for cycle detection in Undirected Graphs,
        # since direction does not matter

        # Graph Representation:
        #   - Each node = element in a disjoint set
        #   - Each edge connects two nodes

        # Problem Abstraction:
        #   - A valid tree must satisfy two conditions:
        #       1. No cycles exist
        #       2. Graph is connected
        #   - Union-Find detects cycles efficiently and ensures connectivity

        # Early Prune -> a valid tree must have exactly n-1 edges
        if len(edges) != n - 1:
            return False

        # Initialize parent array and rank for Union-Find
        # tc: O(V)
        # sc: O(V)

        # parent[i] = representative of the set containing node i
        parent = [i for i in range(n)]

        # rank[i] = size or depth heuristic for union by rank
        rank = [1] * n

        # Find + Path Compression:
        # Returns root of the set containing x
        # Compresses path along the way for efficiency
        # tc: O(α(V))
        def find(x):

            # if parent of node is not self
            while x != parent[x]:

                # path compression, flatten the tree
                parent[x] = parent[parent[x]]

                # set parent, to parent of parent
                x = parent[x]

            # return originals parent, after path compression
            return x

        # Union by Rank:
        # Merges sets containing x and y
        # Returns False if x and y are already in the same set (cycle detected)
        # tc: O(α(N))
        def union(x, y):
            rootX, rootY = find(x), find(y)

            # Early Prune -> cycle detected
            if rootX == rootY:
                return False

            # Merge smaller tree into larger tree to keep tree shallow
            if rank[rootX] > rank[rootY]:
                parent[rootY] = rootX
            elif rank[rootX] < rank[rootY]:
                parent[rootX] = rootY
            else:
                parent[rootY] = rootX
                rank[rootX] += 1
            return True

        # Process all edges
        # tc: O(E)
        for u, v in edges:
            
            # If union failed, that means we tried to join two nodes
            # that already belong to the same component, 
            # which implies we ran into a cycle
            if not union(u, v):
                return False

        # All edges processed without cycle -> valid tree
        # Connectivity is guaranteed by n-1 edges rule

        # overall: tc O(E * α(N))
        # overall: sc O(N)
        return True

    def foreignDictionary(self, words: List[str]) -> str:
        
        # Topological Sort (BFS / Kahn's Algorithm)
        
        # Graph Representation:
        #   - unique character = node in a directed graph
        #   - directed edge (c1 -> c2):
        #       means c1 must appear BEFORE c2 in the alien dictionary order

        # Problem Abstraction:
        #   - Find a valid ordering of characters
        #   - if a cycle exists between character, no valid ordering exists


        # Initialize Graph + In Degree:
        # tc: O(total_chars)
        # sc: O(C), C = number of unique characters

        # graph[c] = set of characters that come after c
        graph = defaultdict(set)
        
        # in_degree[c] = number of incoming edges for c
        in_degree = {c: 0 for word in words for c in word}

        # Build Graph From Adjacent Words
        # W = number of words
        # L = average word length
        # tc: O(W * L)
        for i in range(len(words) - 1):

            # 
            word1, word2 = words[i], words[i+1]
            min_len = min(len(word1), len(word2))
            found_diff = False

            for j in range(min_len):
                c1, c2 = word1[j], word2[j]

                if c1 != c2:
                    
                    # Add edge once (avoid duplicate in-degree increments)
                    if c2 not in graph[c1]:
                        graph[c1].add(c2)
                        in_degree[c2] += 1
                    found_diff = True
                    break

            # Edge case: prefix situation invalid, e.g., "abc" before "ab"
            if not found_diff and len(word1) > len(word2):
                return ""

        # BFS Topological Sort (Kahn's Algorithm):
        # Add all nodes with an In degree == 0 to the queue

        # Process:
        #   1. Pop node from queue
        #   2. Add to ordering
        #   3. Remove outgoing edges
        #   4. Push new zero in-degree nodes

        # sc: O(V)
        queue = deque()

        # tc: O(V)
        for i in range(n):

            # if node has 0 out degree
            if indegree[i] == 0:
                queue.append(i)

        # BFS Topological Sort

        # Tracking nodes we have processed, to check for cycles at the end
        processed = []


        # C = nodes (characters)
        # E = edges (ordering constraints)
        # tc: O(C + E)
        while queue:

            # Remove leftmost node with an In Degree of 0
            c = queue.popleft()

            # Mark node as processed
            processed.append(c)

            # For all directed neighbors of current node,
            # decrease their In Degree by 1
            for nei in graph[c]:

                # decreasing neighbors In Degree
                in_degree[nei] -= 1

                # If neighbor now has an In Degree of 0, append to stack for processing
                if in_degree[nei] == 0:
                    queue.append(nei)

        # If not all nodes were not processed, a cycle exists
        if len(processed) != len(in_degree):
            return ""

        # Return Valid Topological Ordering (one of many orderings)
        res = "".join(processed)

        # C = number of unique characters, W = number of words, L = average word length

        # overall: tc O(C + W*L)
        # overall: sc O(C + W*L)
        return res

    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:

        # Topological Leaf Trimming:
        # In a tree, the roots that produce minimum height
        # are the CENTROIDS of the tree

        # Idea: 
        # Instead of computing the height from every node O(V^2)
        # we iteratively remove leaf nodes (nodes with only one neighbor)
        # layer by layer.
        # Each layer we remove brings us closer to the center of the tree,
        # the last 1 or 2 remaining nodes are the roots that produce Minimum Height Trees

        # Tree Centroids:
        # A centroid of a tree is a node which, if chosen as the root,
        # minimizes the height of the tree
        #   - There can be 1 or 2 centroids in a tree
        #   - For a tree with N nodes, removing leaves layer by layer
        #     eventually exposes the centroid(s)
        #   - The centroid(s) are exactly the roots of the Minimum Height Trees

        # Edge case: single node tree
        if n == 1:
            return [0]

        # Build Undirected Graph:
        # sc: O(n)
        # tc: O(n)


        # graph[u] = neighbors of u
        graph = defaultdict(set)
        for u, v in edges:
            graph[u].add(v)
            graph[v].add(u)

        # Initialize leaves: 
        # Nodes with exactly one neighbor, the outermost layer of the tre
                
        queue = deque([i for i in range(n) if len(graph[i]) == 1])
        
        remaining_nodes = n


        # Trim Leaves Layer By Layer (Topological Sort BFS):
        # Remove current leaves simultaneously, which reveal new layer of leaves
        # tc: O(n)
        while remaining_nodes > 2:

            # Current number of leaves
            leaves_count = len(queue)

            # Track remaining nodes
            remaining_nodes -= leaves_count
            
            # To build next layer of leaves
            new_leaves = deque()
            
            # Remove each leaf in current layer
            for leaf in queue:

                # Grab leaf neighbor (leaf only has one neighbor)
                neighbor = graph[leaf].pop()

                # Remove leaf from neighbor, and from tree
                graph[neighbor].remove(leaf)
                
                # If neighbor has Degree == 1, neighbor has become new leaf
                if len(graph[neighbor]) == 1:

                    # append neighbor to queue for processing
                    new_leaves.append(neighbor)
            
            # Process next layer of leaves
            queue = new_leaves
        
        # <= 2 nodes remain:        
        # The final 1 or 2 nodes are tree centers 
        # and therefore roots of the minimum height trees
        # tc: O(1)
        res = list(queue)

        # overall: tc O(V) 
        # overall: sc O(V)
        return res

    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        # Notes:
        # - Use DFS with memoization to avoid recomputation.
        # - Each cell (i, j) stores the length of the longest increasing path starting there.
        # - Explore 4 directions: up, down, left, right if the next cell is larger.
        #
        # Result: max value across all cells in memo

        if not matrix or not matrix[0]:
            return 0
        
        m, n = len(matrix), len(matrix[0])
        memo = [[0] * n for _ in range(m)]  # memo[i][j] = longest path starting from (i, j)

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        def dfs(i, j):
            # Return cached result
            if memo[i][j] != 0:
                return memo[i][j]
            
            # At least the cell itself
            best = 1
            for dx, dy in directions:
                x, y = i + dx, j + dy
                if 0 <= x < m and 0 <= y < n and matrix[x][y] > matrix[i][j]:
                    best = max(best, 1 + dfs(x, y))
            
            memo[i][j] = best
            return best

        res = 0
        for i in range(m):
            for j in range(n):
                res = max(res, dfs(i, j))
        return res

    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        # Notes:
        # - Treat each cell as a node in a DAG.
        # - Edges go from smaller value -> larger value neighbor.
        # - Topological sorting via Kahn's algorithm counts layers = path length.
        #
        # Result: number of BFS layers processed.

        if not matrix or not matrix[0]:
            return 0

        m, n = len(matrix), len(matrix[0])
        indegree = [[0] * n for _ in range(m)]
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        # Compute indegree for each cell
        for i in range(m):
            for j in range(n):
                for dx, dy in directions:
                    x, y = i + dx, j + dy
                    if 0 <= x < m and 0 <= y < n and matrix[x][y] > matrix[i][j]:
                        indegree[x][y] += 1

        # Collect nodes with indegree 0
        q = deque()
        for i in range(m):
            for j in range(n):
                if indegree[i][j] == 0:
                    q.append((i, j))

        res = 0
        # BFS layer by layer
        while q:
            res += 1
            for _ in range(len(q)):
                i, j = q.popleft()
                for dx, dy in directions:
                    x, y = i + dx, j + dy
                    if 0 <= x < m and 0 <= y < n and matrix[x][y] > matrix[i][j]:
                        indegree[x][y] -= 1
                        if indegree[x][y] == 0:
                            q.append((x, y))
        return res

    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:

        # Topological Sort (BFS / Kahn's Algorithm) for Longest Increasing Path

        # Graph Representation:
        #   - Each cell (i, j) is a node in a Directed Acyclic Graph (DAG)
        #   - Directed edge exists from cell A -> cell B if matrix[A] < matrix[B], so increasing

        # Problem Abstraction:
        #   - With our two representations, that ensures that the topological path
        #     will be the longest increasing path in the matrix

        # Empty Check: no graph, return 0
        if not matrix or not matrix[0]:
            return 0

        # Boundaries
        m, n = len(matrix), len(matrix[0])

        # Constants for direction calculation
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        # Initialize Graph + In Degree:
        # indegree[i][j] = number of incoming edges to cell (i, j)
        indegree = [[0] * n for _ in range(m)]

        # Build indegree array
        # tc: O(V*4) = O(V), V = m*n
        for i in range(m):
            for j in range(n):
                for dx, dy in directions:
                    x, y = i + dx, j + dy
                    
                    if (0 <= x < m and 
                        0 <= y < n and 
                        matrix[x][y] > matrix[i][j]):
                        indegree[x][y] += 1

        # BFS Topological Sort:
        # Start with cells that have indegree 0
        q = deque()
        for i in range(m):
            for j in range(n):
                if indegree[i][j] == 0:
                    q.append((i, j))

        # Track number of layers = length of longest increasing path
        longest_path = 0

        # C = number of nodes (cells)
        # E = number of edges (neighboring increasing cells)
        # tc: O(C + E)
        while q:
            
            # Increase longest path
            longest_path += 1
            
            # For all elements in queue
            for _ in range(len(q)):
                
                # Pop farthest left node? (what does this mean in this context)
                i, j = q.popleft()
                
                # Explore:
                # check all neighbors
                for dx, dy in directions:
                    
                    # Generate coordinates for neighbors in 4 directions
                    x, y = i + dx, j + dy
                    
                    # Check if valid in boundary
                    if (0 <= x < m and 
                        0 <= y < n and 
                        matrix[x][y] > matrix[i][j]):
                        
                        # decrease In Degree of neighbor
                        indegree[x][y] -= 1

                        # If neighbor now has an In Degree == 0, append to queue for processing
                        if indegree[x][y] == 0:
                            q.append((x, y))

        # overall: tc O(m*n) - each cell processed at most once
        # overall: sc O(m*n) - indegree array + queue
        return longest_path

    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:
        
        # Topological Sort (BFS / Kahn's Algorithm)

        # Unique Topological Ordering:
        #   - A graph has a unique topological ordering,
        #     if at each step, there is exactly one node with an In Degree of 0.
        #     So the queue must at most only have 1 node at a time

        # If the topological order matches nums order exactly, return True.
        # Otherwise, return False.

        # Graph Representation:
        #   - Each unique number = node in a directed graph
        #   - A sequence [u, v] = directed edge u -> v
        #       means u must come before v in any valid order

        # Problem Abstraction:
        #   - Determine if there is a unique topological order
        #     that matches the given nums array exactly
        #   - A unique topological order exists if at each step
        #     there is only one node with indegree 0

        n = len(nums)


        # Initialize Graph + In Degree:
        # tc: O(sum(len(seq))) <= 1e5
        # sc: O(n + sum(len(seq))) <= 1e5

        # graph[node] = set of neighbors that come after node
        graph = defaultdict(set)

        # in_degree[c] = number of pre requisite classes for c, nodes are 1-indexed
        in_degree = [0] * (n + 1)

        # Build Graph from sequences
        # tc: O(sum(len(seq)))
        for seq in sequences:

            # For num i, check [0, i]
            for i in range(len(seq) - 1):

                # Build edge i -> i+1
                u, v = seq[i], seq[i + 1]

                # If edge has not already been added
                if v not in graph[u]:

                    # Add In Degree
                    graph[u].add(v)

                    # Increase In Degree
                    in_degree[v] += 1


        # BFS Topological Sort (Kahn's Algorithm):
        # Add all nodes with an In degree == 0 to the queue

        # Initialize queue with nodes having indegree 0
        # Unique ordering check: queue must have exactly one node at each step
        queue = deque([i for i in range(1, n + 1) if in_degree[i] == 0])
        
        # Tracking nodes we have processed, to check for cycles at the end
        topo_order = []

        # BFS Topological Sort
        while queue:

            # Unique Topological Ordering Early Exit
            # For unique ordering, at any point the queue must only have one node
            # If multiple nodes have 0 In Degreee, multiple sequences are possible
            if len(queue) > 1:
                # Multiple nodes have 0 In Degree, multiple sequences possible, unique is not possible
                return False

            # Remove leftmost node with an In Degree of 0
            node = queue.popleft()

            # Mark node as processed
            topo_order.append(node)

            # For all directed neighbors of current node,
            # decrease their In Degree by 1
            for nei in graph[node]:

                # decreasing neighbors In Degree
                in_degree[nei] -= 1
                
                # If neighbor now has an In Degree of 0, 
                # append to stack for processing
                if in_degree[nei] == 0:
                    queue.append(nei)

        # If not all nodes were not processed, a cycle exists
        # tc: O(1)
        if len(topo_order) != len(nums):
            return False

        # Check if reconstructed order matches nums
        # tc: O(V)
        if topo_order != n:
            return False

        # Complexity Analysis
        # Time Complexity:
        #   O(sum(len(seq))) to build graph
        #   + O(n + E) for BFS topo sort
        #   = O(sum(len(seq))) overall
        #
        # Space Complexity:
        #   O(n + E) for graph and in-degree array

        # overall: tc O(sum(len(seq)))
        # overall: sc O(V + sum(len(seq)))
        return True

    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:

        # Topological Sort (BFS / Kahn's Algorithm):

        # Graph Representation:
        #   - unique node = node in a directed graph
        #   - edge u -> v = u can go to v

        # Problem Abstraction:
        #   - A node is SAFE if every path from it eventually reaches a terminal node.
        #   - Terminal nodes = nodes with no outgoing edges
        #   - Instead of detecting cycles directly, reverse the graph:
        #       - terminal nodes (outDegree = 0) are inherently safe
        #       - nodes pointing to safe nodes eventually become safe
        #   - Use topological BFS to remove edges layer by layer starting from terminal nodes

        # Idea:
        # Instead of detecting cycles directly, reverse the graph.
        # Since we know that terminal nodes (outdegree = 0) are always safe,
        # we know that nodes that point to that terminal node are also safe.
        
        # This then becomes a topological style BFS where we remove
        # edges starting from terminal nodes.
        # So instead of queuing nodes with In Degree == 0, 
        # we instead queue nodes with Out Degree == 0

        # Original graph:
        #   u -> v   (u depends on v)

        # Reversed graph:
        #   v -> u

        # Build A Reverse Graph + Out Degree Count
        # tc: O(V + E)
        # sc: O(V + E)

        n = len(graph)

        # reverse_graph[v] contains all nodes pointing to v
        reverse_graph = [[] for _ in range(n)]

        # outDegree[u] = number of outgoing edges in original graph
        outDegree = [0] * n

        # Build Reverse Graph + Count Outgoing Edges

        # outDegree[u] stores the number of outgoing edges for node u in the original graph.
        # Nodes with outDegree == 0 are terminal nodes and are inherently safe.
        for u in range(n):

            # 
            for v in graph[u]:
                # Add u as a predecessor of v in the reversed graph
                reverse_graph[v].append(u)

            # Count outgoing edges for u in original graph
            outDegree[u] = len(graph[u])  
        
        
        # BFS Topological Sort (Kahn's Algorithm):
        # Terminal nodes have out degree = 0, these are guaranteed safe.
        # So we add all terminal nodes with Out Degree == 0, to the queue
        
        # Process:
        #   1. Pop node from queue
        #   2. Add to ordering
        #   3. Remove outgoing edges
        #   4. Push new zero in-degree nodes

        # sc: O(V)
        queue = deque()

        # tc: O(V)
        for i in range(n):

            # if node has 0 out degree
            if outDegree[i] == 0:
                queue.append(i)
        
        # BFS Topological Sort
        
        # Tracking nodes we have marked as safe
        safe = [False] * n
        
        # C = nodes (characters)
        # E = edges (?)
        # tc: O(C + E)
        while queue:

            # remove leftmost node with an Out Degree of 0
            node = queue.popleft()

            # Mark node as processed
            safe[node] = True
            
            # Reduce outgoing edge count for predecessors in reversed graph
            for prev in reverse_graph[node]:

                # decreasing neighbors Out Degree
                outDegree[prev] -= 1

                # If neighbor now has an Out Degree of 0, append to stack for processing
                if outDegree[prev] == 0:
                    queue.append(prev)
        
        # Collect all safe nodes:
        # ensure ascending order
        res = [i for i in range(n) if safe[i]]

        # V = n
        # E = total edges
        # overall: tc O(V + E)
        # overall: sc O(V + E)    
        return sorted(res)

    def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:

        # Topological Sort (BFS Kahn's Algorithm)
        # For each person v: find the quietest person among
        #  { all people richer than v } + { v }
        
        # Idea:
        # Richness defines a directed acyclic order
        # If we process people from richer -> poorer (topological order)
        # we can propagate the quietest known person downward

        # This turns the problem into:
        #   - Topological BFS where each node passes its best answer to its poorer neighbors

        n = len(quiet)
        
        # Build graph:
        # tc: O(E)
        # sc: O(V + E)

        # graph[u] = people poorer than u
        graph = [[] for _ in range(n)]

        # indegree[v] = number of richer people pointing to v
        indegree = [0] * n
        
        # Edge u -> v means u is richer than v
        for u, v in richer:
            graph[u].append(v)  # u richer than v
            indegree[v] += 1
        
        # result array
        # sc: O(V)
        answer = [i for i in range(n)]

        # Initialize answer array:
        # Start with people that have no richer individuals (In Degree == 0)
        # tc: O(V)        
        queue = deque([i for i in range(n) if indegree[i] == 0])
        
        # BFS Topological Sort
        while queue:

            # Pop node with 0 In Degree
            u = queue.popleft()
            
            # Check people poorer
            for v in graph[u]:
                
                # Propagate better (quieter) answer
                if quiet[answer[u]] < quiet[answer[v]]:
                    answer[v] = answer[u]
                
                # Standard topological reduction
                indegree[v] -= 1
                if indegree[v] == 0:
                    queue.append(v)
        

        # V = number of people
        # E = number of richer relationships
        
        # overall: tc O(V + E)
        # overall: sc O(V + E)
        return answer

    def catMouseGame(self, graph: List[List[int]]) -> int:

        # Reverse Topological BFS on Game States

        # Instead of simulating the game forward, we solve states backwards from known outcomes

        # A game state is defined as:
        #   (mouse_position, cat_position, turn)

        # turn = 0 => mouse moves next
        # turn = 1 => cat moves next

        # Each state has one of three results:
        #   DRAW = 0
        #   MOUSE = 1 (mouse wins)
        #   CAT = 2 (cat wins)

        # Idea:
        # Treat all states as nodes in a state graph

        # Terminal states are known immediately:
        #   - mouse reaches hole (node 0) => mouse wins
        #   - cat catches mouse => cat wins

        # From these known states, propagate results backward
        # to parent states using reverse BFS (topological reasoning)

        # Essentially:
        #   Topological elimination on a game state graph

        n = len(graph)
        
        # Constants For Game State
        DRAW, MOUSE, CAT = 0, 1, 2
        
        # State Arrays:
        # sc: O(n^3)

        # color[m][c][t] = result of state
        color = [[[DRAW]*2 for _ in range(n)] for _ in range(n)]
        
        # degree[m][c][t] = number of available moves
        degree = [[[0]*2 for _ in range(n)] for _ in range(n)]
        
        # Initialize Move Counts
        for m in range(n):
            for c in range(n):

                # Mouse Moves
                degree[m][c][0] = len(graph[m])

                # Cat cannot enter hole
                degree[m][c][1] = len(graph[c]) - (0 in graph[c])
        
        # Initialize Terminal States:
        # Known outcomes:
        #   1. Mouse at hole -> MOUSE wins
        #   2. Cat catches mouse -> CAT wins

        # These become starting points for reverse BFS
        # tc: O(n)

        # Queue of known results (terminal states)
        queue = deque()
        
        # Terminal states
        for i in range(n):
            for t in range(2):
                # Mouse at hole -> mouse wins
                color[0][i][t] = MOUSE
                queue.append((0, i, t, MOUSE))
                
                # Cat catches mouse -> cat wins
                if i != 0:
                    color[i][i][t] = CAT
                    queue.append((i, i, t, CAT))
        


        # Reverse BFS on State Graph:

        # Process known states nad update their parent states

        # Parent logic:
        #   - If current result is winning for the player whose turn it was previously,
        #    parent becomes winning
        #
        #   - Otherwise, reduce degree
        #     


        # BFS / Topological sort on states
        while queue:
            
            # Current Resolve State
            mouse, cat, turn, result = queue.popleft()
            
            # Find Parent States (determine states that can reach the current state):

            # mouse just moved:
            if turn == 0:

                # previous turn was cat
                prev_turn = 1

                # Determine where cat could have come from:
                for prev_cat in graph[cat]:

                    # Cat cannot move to hole
                    if prev_cat == 0:
                        continue  

                    # Skip already resolved states:
                    if color[mouse][prev_cat][prev_turn] != DRAW:
                        continue

                    # If current state is Cat win,
                    # can can choose this move and force win
                    if result == CAT:
                        color[mouse][prev_cat][prev_turn] = CAT
                        queue.append((mouse, prev_cat, prev_turn, CAT))

                    else:

                        # Otherwise this move is bad for cat
                        # Remove this option, remove one available option
                        degree[mouse][prev_cat][prev_turn] -= 1

                        # If all moves are bad: mouse wins
                        if degree[mouse][prev_cat][prev_turn] == 0:
                            color[mouse][prev_cat][prev_turn] = MOUSE
                            queue.append((mouse, prev_cat, prev_turn, MOUSE))

            # cat just moved:
            else:

                # previous turn was cat
                prev_turn = 0

                # Determine where mouse could have come from
                for prev_mouse in graph[mouse]:

                    # Skip already resolved states
                    if color[prev_mouse][cat][prev_turn] != DRAW:
                        continue

                    # If current state is MOUSE win,
                    # mouse can choose this move and force win
                    if result == MOUSE:
                        color[prev_mouse][cat][prev_turn] = MOUSE
                        queue.append((prev_mouse, cat, prev_turn, MOUSE))
                    
                    else:

                        # Other this move is bad for mouse
                        # Remove this option, remove one available option
                        degree[prev_mouse][cat][prev_turn] -= 1

                        # If all moves lose: cat wins
                        if degree[prev_mouse][cat][prev_turn] == 0:
                            color[prev_mouse][cat][prev_turn] = CAT
                            queue.append((prev_mouse, cat, prev_turn, CAT))
        

        # Final Result:
        # Initial State
        #   mouse => 1
        #   cat   => 2
        #   mouse moves first

        # Result Starting From: 
        #   mouse = 1
        #   cat=2
        #   mouse turn
        res = color[1][2][0]
        
        # overall: tc O(n^3) since there are O(n^2 * 2) states and each state checks neighbors
        # overall: sc O(n^3) for color and degree arrays
        return res

    def countPaths(self, n: int, roads: List[List[int]]) -> int:
         MOD = 10**9 + 7

        # Dijkstras + Topological DP on Shortest Path

        # Step 1: Compute shortest path distances from node 0
        # Step 2: Treat nodes as DAG ordered by distance
        # Step 3: Propagate number of ways along edges consistent with shortest paths

        # Key Insight:
        # After Dijkstra, any edge u->v such that dist[u] + t == dist[v]
        # can only be used along a shortest path.

        # Topological DP:
        #   - process nodes in increasing distance (topological order)
        #   - propagate counts along shortest paths edges

        # Build adjacency list with travel times:

        # graph[u] = [(neighbor, travel_time), ...] 

        # sc: O(V + E)
        graph = defaultdict(list)

        # tc: O(E)
        for u, v, t in roads:
            graph[u].append((v, t))
            graph[v].append((u, t))

        # Dijkstra to find shortest distances from node 0

        # dist[u] = shortest distance from node 0 to u
        # sc: O(V)
        dist = [float('inf')] * n
        dist[0] = 0
        heap = [(0, 0)]  # (distance, node)

        # tc: O(E log V)
        while heap:

            # 
            d, u = heapq.heappop(heap)
            if d > dist[u]:
                continue
            for v, t in graph[u]:
                if dist[u] + t < dist[v]:
                    dist[v] = dist[u] + t
                    heapq.heappush(heap, (dist[v], v))

        # Sort nodes by distance (topological order by shortest path)
        # Nodes can now be treated as DAG ordered by dist:
        #   edges along shortest paths only go from smaller to larger distance
        # tc: O(V log V)
        # sc: O(V)
        nodes_by_dist = sorted(range(n), key=lambda x: dist[x])

        # DP to count ways along shortest paths
        
        # ways[u] = number of shortest paths from 0 to u
        ways = [0] * n

        # Start from node 0
        ways[0] = 1

        # Propagate along edges where dist[u] + t == dist[v]
        # tc: O(E)
        # sc: O(V)
        for u in nodes_by_dist:
            for v, t in graph[u]:

                # Only propagate along shortest paths
                if dist[u] + t == dist[v]:
                    ways[v] = (ways[v] + ways[u]) % MOD

        # Number of ways to reach destination n-1
        res = ways[n - 1]

        
        # Let V = n nodes, E = len(roads) edges
        
        # tc:
        #   O(E log V)  → Dijkstra
        #   + O(V log V) → sorting nodes
        #   + O(E)      → DP propagation
        #   = O(E log V)
        
        # sc:
        #   O(V + E) → adjacency list, distance array, ways array

        # overall: tc (E log V)
        # overall sc O(V + E)
        return res

    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:
        
        # Topological Sort (BFS / Kahn's Algorithm)
        #
        # Graph Representation:
        #   - item = node in item graph
        #   - group = node in group graph
        #
        # Problem Abstraction:
        #   - Items must respect dependency ordering
        #   - Items in same group must appear together
        #
        # Key Idea:
        #   - Perform TWO topological sorts:
        #       1. group-level ordering
        #       2. item-level ordering
        #
        #   Group ordering determines group blocks.
        #   Item ordering determines order inside blocks.



        # Assign unique groups to ungrouped items:
        for i in range(n):

            # group[i] == -1 means item has no group.
            if group[i] == -1:

                # Treat each as its own unique group
                group[i] = m
                m += 1

        # Graphs + In Degrees
        
        item_graph = defaultdict(list)
        group_graph = defaultdict(list)

        # item_graph: dependency between items
        item_indegree = [0] * n

        # group_graph: dependency between groups
        group_indegree = [0] * m

        # group => list of items
        group_items = defaultdict(list)


        for i in range(n):
            group_items[group[i]].append(i)

        # Build Item Graph + Group Graph:
        #   - If two dependent items belong to different groups:
        #       create edge between groups.
        #   - Otherwise:
        #       create edge between items.
        for curr in range(n):
            for prev in beforeItems[curr]:

                # item dependency
                item_graph[prev].append(curr)
                item_indegree[curr] += 1

                # cross-group dependency
                if group[prev] != group[curr]:
                    group_graph[group[prev]].append(group[curr])
                    group_indegree[group[curr]] += 1

        # Topological Sort Helper (BFS)

        def topo_sort(nodes, graph, indegree):

            queue = deque([x for x in nodes if indegree[x] == 0])
            order = []

            while queue:
                node = queue.popleft()
                order.append(node)

                for nei in graph[node]:
                    indegree[nei] -= 1
                    if indegree[nei] == 0:
                        queue.append(nei)

            # cycle detection
            if len(order) != len(nodes):
                return []

            return order

        # Topological Sort Groups:

        group_order = topo_sort(range(m), group_graph, group_indegree)
        if not group_order:
            return []

        # Topological Sort Items:

        item_order = topo_sort(range(n), item_graph, item_indegree)
        if not item_order:
            return []

        # Organize Items by Group Order
        
        # item_order already respects dependencies.
        # We now place items together by group.

        ordered_group_items = defaultdict(list)
        for item in item_order:
            ordered_group_items[group[item]].append(item)

        result = []
        for g in group_order:
            result.extend(ordered_group_items[g])

        # overall: tc O(n + total dependencies)
        # overall: sc O(n + total dependencies)
        return result

    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:

        # Topological Sort (BFS / Kahn's Algorithm)
        #
        # Graph Representation:
        #   - unique class = node in a directed graph
        #   - directed edge (a -> b):
        #       means a must be taken BEFORE b
        #
        # Problem Abstraction:
        #   - Determine if course u is a prerequisite of course v
        #   - Includes DIRECT and INDIRECT prerequisites
        #
        # Key Idea:
        #   - Perform BFS topological sort
        #   - While processing nodes,
        #     propagate prerequisite sets forward.
        #
        #   If:
        #       a -> b
        #   then:
        #       prereqs[b] includes prereqs[a] + {a}

        # --------------------------------------------------
        # Initialize Graph + In Degree
        # --------------------------------------------------

        graph = defaultdict(list)
        indegree = [0] * numCourses

        for a, b in prerequisites:
            graph[a].append(b)
            indegree[b] += 1

        # --------------------------------------------------
        # prereqs[i] = all prerequisites of course i
        # --------------------------------------------------

        prereqs = [set() for _ in range(numCourses)]

        # --------------------------------------------------
        # BFS Topological Sort (Kahn's Algorithm)
        # --------------------------------------------------

        queue = deque()

        for i in range(numCourses):
            if indegree[i] == 0:
                queue.append(i)

        # --------------------------------------------------
        # Process:
        #   1. Pop node
        #   2. Propagate prereqs to neighbors
        #   3. Reduce indegree
        #   4. Push new zero indegree nodes
        # --------------------------------------------------

        while queue:

            curr = queue.popleft()

            for nei in graph[curr]:

                # curr itself is prerequisite of neighbor
                prereqs[nei].add(curr)

                # all prereqs of curr propagate forward
                prereqs[nei].update(prereqs[curr])

                indegree[nei] -= 1

                if indegree[nei] == 0:
                    queue.append(nei)

        # --------------------------------------------------
        # Answer Queries
        # --------------------------------------------------

        res = []

        for u, v in queries:
            res.append(u in prereqs[v])

        # overall: tc O(V^2 + Q)
        #   V <= 100 so set propagation is safe
        #
        # overall: sc O(V^2)

        return res