Consider a directed graph, with nodes labelled 0, 1, ..., n-1.  In this graph, each edge is either red or blue, and there could be self-edges or parallel edges.
Each [i, j] in red_edges denotes a red directed edge from node i to node j.  Similarly, each [i, j] in blue_edges denotes a blue directed edge from node i to node j.
Return an array answer of length n, where each answer[X] is the length of the shortest path from node 0 to node X such that the edge colors alternate along the path (or -1 if such a path doesn't exist).
Example 1:
Input: n = 3, red_edges = [[0,1],[1,2]], blue_edges = []
Output: [0,1,-1]
Example 2:
Input: n = 3, red_edges = [[0,1]], blue_edges = [[2,1]]
Output: [0,1,-1]
Example 3:
Input: n = 3, red_edges = [[1,0]], blue_edges = [[2,1]]
Output: [0,-1,-1]
Example 4:
Input: n = 3, red_edges = [[0,1]], blue_edges = [[1,2]]
Output: [0,1,2]
Example 5:
Input: n = 3, red_edges = [[0,1],[0,2]], blue_edges = [[1,0]]
Output: [0,1,1]
Constraints:
1 <= n <= 100
red_edges.length <= 400
blue_edges.length <= 400
red_edges[i].length == blue_edges[i].length == 2
0 <= red_edges[i][j], blue_edges[i][j] < n
class Solution:
    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
        graph_red = defaultdict(list)
        graph_blue = defaultdict(list)
        
        for a, b in red_edges:
            graph_red[a].append(b)
        
        for a, b in blue_edges:
            graph_blue[a].append(b)
            
        def bfs(target):
            BLUE = 1
            RED = 2
            seen = set()
            queue = deque([(0, 0, BLUE), (0,0,RED)])
            
            while queue:
                node, steps, color = queue.popleft()
                
                if node == target:
                    return steps
                
                if color == RED:
                    for next_node in graph_blue[node]:
                        if (next_node, BLUE) not in seen:
                            seen.add((next_node, BLUE))
                            queue.append((next_node, steps + 1, BLUE))
                else:
                    for next_node in graph_red[node]:
                        if (next_node, RED) not in seen:
                            seen.add((next_node, RED))
                            queue.append((next_node, steps + 1, RED))
            
            return -1
                            
            
        res = []
        
        for i in range(n):
            res.append(bfs(i))
        
        return res
class Solution:
    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
        graph_red = defaultdict(list)
        graph_blue = defaultdict(list)
        
        for a, b in red_edges:
            graph_red[a].append(b)
        
        for a, b in blue_edges:
            graph_blue[a].append(b)
            
        def bfs(target):
            BLUE = 1
            RED = 2
            seen = set()
            queue = deque([(0, 0, BLUE), (0,0,RED)])
            
            while queue:
                node, steps, color = queue.popleft()
                
                if node == target:
                    return steps
                
                if color == RED:
                    for next_node in graph_blue[node]:
                        if (next_node, BLUE) not in seen:
                            seen.add((next_node, BLUE))
                            queue.append((next_node, steps + 1, BLUE))
                else:
                    for next_node in graph_red[node]:
                        if (next_node, RED) not in seen:
                            seen.add((next_node, RED))
                            queue.append((next_node, steps + 1, RED))
            
            return -1
                            
            
        res = []
        
        for i in range(n):
            res.append(bfs(i))
        
        return res