Shortest Path with Alternating Colors

A directed graph has n nodes labeled 0 through n - 1. Each pair [u, v] in redEdges is a red edge from u to v, and each pair in blueEdges is a blue edge. Self-loops and repeated edges are allowed.

Return an array of length n. At index x, give the fewest edges in a path from node 0 to node x whose consecutive edges alternate colors. If no such path exists, use -1.

The first edge may have either color. The empty path from node 0 to itself has length 0.

Example 1:

Input: n = 4
redEdges = [[0,1],[2,3]]
blueEdges = [[1,2]]

Output: [0,1,2,3]

Explanation: The route 0 → 1 → 2 → 3 uses red, blue, then red. Its prefixes reach nodes 1, 2, and 3 in 1, 2, and 3 edges.

Example 2:

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

Output: [0,1,3]

Explanation: To reach node 2, take the red edge 0 → 1, the blue self-loop 1 → 1, and the red edge 1 → 2. This alternating route has length 3. Node 1 is reachable in one edge.

Example 3:

Input: n = 4
redEdges = [[0,1]]
blueEdges = [[0,2]]

Output: [0,1,1,-1]

Explanation: Nodes 1 and 2 are each one edge from node 0, and either color may be used first. Node 3 is disconnected, so its answer is -1.

Constraints:

• 1 <= n <= 100
• 0 <= redEdges.length, blueEdges.length <= 400
• Every edge contains exactly two integer endpoints.
• Each endpoint is between 0 and n - 1.
• Self-loops and parallel edges are allowed.