#176MediumGraphs· Topological Sort with a Priority Queue

Smallest-First Build Order

A build system must compile `n` modules numbered `0` to `n - 1`. Some modules depend on others: a pair `[a, b]` in `requires` means module `b` has to be built **before** module `a`. To make builds reproducible the system follows one extra rule: whenever several modules are ready to build (all their prerequisites are done), it builds the one with the **smallest number** first. Return the order in which the modules get built. If the dependencies contain a cycle and not every module can be built, return an empty list. All pairs in `requires` are distinct.

Input format

`n`: the number of modules; `requires`: an array of pairs `[a, b]` meaning b must be built before a.

Output format

An array of the `n` module numbers in build order, or an empty array if a dependency cycle makes it impossible.

Examples

Input: n = 4, requires = [[1, 0], [2, 0], [3, 1], [3, 2]]

Output: [0, 1, 2, 3]

Only module 0 is ready at first. Then 1 and 2 are ready and 1 is smaller. Module 3 needs both, so the order is 0, 1, 2, 3.

Input: n = 3, requires = [[0, 2]]

Output: [1, 2, 0]

Modules 1 and 2 are ready first and 1 is smaller. Module 0 needs 2, so after 1 we build 2 and finally 0: 1, 2, 0.

Input: n = 2, requires = [[0, 1], [1, 0]]

Output: []

Each module waits for the other, a cycle, so nothing can be built and the result is empty.

Constraints

1 <= n <= 2000
0 <= requires.length <= 10^4
0 <= a, b < n and a != b
All pairs are distinct.

Study first

#graph
#topological-sort
#heap
#dependency-resolution