There are n items 0 .. n-1. Item i belongs to group group[i] (a non-negative integer). before is a list of pairs [a, b] meaning item a must appear before item b.
Return a list of all n items such that:
- all items of the same group are contiguous in the list, and
- every pair in
beforeis respected.
If several answers exist return any; if none exists return [].
Examples
Input: n = 5, group = [0, 0, 1, 1, 1], before = [[3, 0], [2, 3]]
Output: [2, 3, 4, 0, 1]
Explanation: group 1 must precede group 0 because 3 comes before 0; inside group 1, 2 precedes 3.
Input: n = 4, group = [0, 1, 0, 1], before = [[0, 1], [1, 2]]
Output: []
Explanation: group 0 would have to come both before and after group 1.
Your answer is checked against the two rules, so any valid list passes.
Constraints
1 <= n <= 3000,0 <= group[i] < n,0 <= len(before) <= 6000- Target: O(n + len(before)) time.
Goals
- Lift item-level constraints to constraints between groups
- Run one topological sort on groups and one inside each group
- Detect impossibility at either level