1
class Solution:
2
    def sortItems(
3
        self, n: int, m: int, group: List[int], beforeItems: List[List[int]]
4
    ) -> List[int]:
5
        before = {i: set() for i in range(n)}
6
        after = {i: set() for i in range(n)}
7
        beforeG = {i: set() for i in range(m)}
8
        afterG = {i: set() for i in range(m)}
9
        groups = {i: set() for i in range(m)}
10
        qg = collections.deque()
11
        lazy = collections.deque()
12
        for i in range(n):
13
            if group[i] != -1:
14
                groups[group[i]].add(i)
15
            for x in beforeItems[i]:
16
                before[i].add(x)
17
                after[x].add(i)
18
                if group[x] != group[i] and group[x] != -1 and group[i] != -1:
19
                    beforeG[group[i]].add(group[x])
20
                    afterG[group[x]].add(group[i])
21
        for i in range(n):
22
            if group[i] == -1 and not before[i]:
23
                lazy.append(i)
24

25
        for i in range(m):
26
            if not beforeG[i]:
27
                qg.append(i)
28
        ans = []
29
        while qg:
30
            while lazy:
31
                i = lazy.popleft()
32
                ans.append(i)
33
                for j in after[i]:
34
                    before[j].remove(i)
35
                    if not before[j] and group[j] == -1:
36
                        lazy.append(j)
37
            g = qg.popleft()
38
            q = collections.deque()
39
            for member in groups[g]:
40
                if not before[member]:
41
                    q.append(member)
42
            while q:
43
                i = q.popleft()
44
                ans.append(i)
45
                groups[g].remove(i)
46
                for j in after[i]:
47
                    before[j].remove(i)
48
                    if not before[j]:
49
                        if group[j] == g:
50
                            q.append(j)
51
                        if group[j] == -1:
52
                            lazy.append(j)
53
            if groups[g]:
54
                return []
55
            for p in afterG[g]:
56
                beforeG[p].remove(g)
57
                if not beforeG[p]:
58
                    qg.append(p)
59
        while lazy:
60
            i = lazy.popleft()
61
            ans.append(i)
62
            for j in after[i]:
63
                before[j].remove(i)
64
                if not before[j] and group[j] == -1:
65
                    lazy.append(j)
66
        return ans if len(ans) == n else []