# 1129 Shortest Path with Alternating Colors

You are given an integer `n`, the number of nodes in a directed graph where the nodes are labeled from `0` to `n - 1`. Each edge is red or blue in this graph, and there could be self-edges and parallel edges.

You are given two arrays `redEdges` and `blueEdges` where:

• `redEdges[i] = [ai, bi]` indicates that there is a directed red edge from node `ai` to node `bi` in the graph, and
• `blueEdges[j] = [uj, vj]` indicates that there is a directed blue edge from node `uj` to node `vj` in the graph.

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 does not exist.

Example 1:

``````Input: n = 3, redEdges = [[0,1],[1,2]], blueEdges = []
Output: [0,1,-1]
``````

Example 2:

``````Input: n = 3, redEdges = [[0,1]], blueEdges = [[2,1]]
Output: [0,1,-1]
``````

Constraints:

• `1 <= n <= 100`
• `0 <= redEdges.length, blueEdges.length <= 400`
• `redEdges[i].length == blueEdges[j].length == 2`
• `0 <= ai, bi, uj, vj < n`
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 `````` ``````class Solution: def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]: graph = { 1: defaultdict(set), # red -1: defaultdict(set), # blue } for se, ee in redEdges: graph[se].add(ee) for se, ee in blueEdges: graph[-1][se].add(ee) res = [-1] * n res = 0 queue = [(0, 1), (0, -1)] seen = set() path_len = 1 while queue: temp_queue = [] for node, color in queue: for child in graph[-color][node]: if (node, child, -color) not in seen: seen.add((node, child, -color)) if res[child] == -1 or path_len < res[child]: res[child] = path_len temp_queue.append((child, -color)) queue = temp_queue path_len += 1 return res``````