Determine Valid Build Order

Given a collection of BUILD files and the relationships between them, produce an ordering in which every file is built only after the files it depends on.

Input

• An integer n denoting the total number of BUILD files.
• A two-dimensional array dependencies, where each pair dependencies[i] = [a, b] means BUILD file a requires BUILD file b to be built first.

Output

Return an array containing a valid build sequence. If no valid sequence can be produced, return an empty array.

Example

Input: n = 4, dependencies = [[1, 0], [2, 0], [3, 1], [3, 2]]
Output: [0, 1, 2, 3] or [0, 2, 1, 3]

Both outputs are valid because file 0 precedes files 1 and 2, and file 3 comes after both of its dependencies.

Note

• 1 <= n <= 10^4
• The dependency relationships are guaranteed to contain no cycles.