Sort Items by Groups Respecting Dependencies

There are n items each belonging to zero or one of m groups, where group[i] is the group that the i-th item belongs to. Items that do not belong to any group are assigned group[i] = -1. Items with -1 should each be treated as their own unique group.

You are given a 2D array beforeItems, where beforeItems[i] is a list of all items that must come before the i-th item in the sorted order.

Return any valid ordering of the items such that:

1. Items in the same group are adjacent to each other in the result.

2. All dependency constraints from beforeItems are satisfied.

If no valid solution exists, return an empty array.

Examples

Example 1:

Input: n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]]

Output: [6,3,4,1,5,2,0,7]

Explanation: Items 3, 4, 6 are in group 0. Items 2, 5 are in group 1. Items 0, 1, 7 each form their own group. The output respects all dependency constraints: item 6 comes before items 1, 3, and 4; item 5 comes before item 2; item 3 comes before item 4; and item 6 comes before item 3.

Example 2:

Input: n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3],[],[4],[]]

Output: []

Explanation: There is a circular dependency between groups — group 0 needs something from group 1 (item 4 depends on item 3 which is in group 0, but item 6 in group 0 depends on item 4 indirectly through group ordering). This makes it impossible to satisfy all constraints.

Constraints

• 1 <= m <= n <= 30000
• group.length == n
• -1 <= group[i] <= m - 1
• beforeItems.length == n
• 0 <= beforeItems[i].length <= n - 1
• 0 <= beforeItems[i][j] <= n - 1
• i !== beforeItems[i][j]
• beforeItems[i] does not contain duplicates