1
class Solution:
2
    def shortestAlternatingPaths(
3
        self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]
4
    ) -> List[int]:
5
        g = [[[] for _ in range(2)] for _ in range(n)]
6

7
        for i, j in redEdges:
8
            g[i][0] += [j]
9
        for i, j in blueEdges:
10
            g[i][1] += [j]
11
        distance = [float("inf") for _ in range(n)]
12
        distance[0] = 0
13
        q = queue.Queue()
14
        q.put((0, 0, False))
15
        q.put((0, 0, True))
16

17
        redS = set([0])
18
        blueS = set([0])
19
        while not q.empty():
20
            node, dist, red = q.get()
21
            if red:
22
                neighbours = g[node][0]
23
                redS.add(node)
24
                curr = blueS
25
            else:
26
                neighbours = g[node][1]
27
                blueS.add(node)
28
                curr = redS
29
            for neighbour in neighbours:
30
                if dist + 1 < distance[neighbour]:
31
                    distance[neighbour] = dist + 1
32
                    q.put((neighbour, dist + 1, not red))
33
                if not (neighbour in curr):
34
                    q.put((neighbour, dist + 1, not red))
35
        for i in range(n):
36
            if distance[i] == float("inf"):
37
                distance[i] = -1
38
        return distance