Lexicographically Smallest Course Order From Prerequisite Pairs

There are `n` courses labeled `0` to `n - 1`. Each pair `[a, b]` in `prerequisites` means that course `b` must be taken before course `a`. Return an order in which all `n` courses can be taken, or an empty list if no such order exists. Several orders can be valid. Return the lexicographically smallest one: compare two orders position by position, and at the first position where they differ, the order with the smaller course label there is the smaller order. ### Function Signature ```python def course_order(n: int, prerequisites: list[list[int]]) -> list[int]: ``` ### Rules - A valid order contains every course from `0` to `n - 1` exactly once, and for every pair `[a, b]`, course `b` appears before course `a`. - If no valid order exists (some courses depend on each other in a cycle), return `[]`. - Among all valid orders, return the lexicographically smallest. ### Constraints - `1 <= n <= 100000` - `0 <= len(prerequisites) <= 200000` - Each pair `[a, b]` has `0 <= a < n`, `0 <= b < n` and `a != b`. - No pair appears more than once. ### Examples **Example 1** ```text Input: n = 5, prerequisites = [[2, 4], [0, 4], [1, 0], [3, 1], [3, 2]] Output: [4, 0, 1, 2, 3] ``` Every other course depends on course `4`, directly or indirectly, so it must come first. Course `3` needs courses `1` and `2`, and course `1` needs course `0`, so course `3` must come last. The valid orders are `[4, 0, 1, 2, 3]`, `[4, 0, 2, 1, 3]` and `[4, 2, 0, 1, 3]`, and the first of them is the smallest. **Example 2** ```text Input: n = 3, prerequisites = [[0, 1], [1, 2], [2, 1]] Output: [] ``` Courses `1` and `2` each require the other first, so no valid order exists. **Example 3** ```text Input: n = 3, prerequisites = [] Output: [0, 1, 2] ```