Shortest Path with Alternating Colors

You get a directed graph with n nodes, numbered 0 to n - 1. Every edge is either red or blue. Each pair [u, v] in redEdges is a red edge from u to v. The pairs in blueEdges are the blue edges.

Return an array answer with one number per node. For each node x, answer[x] is the fewest edges on an alternating path from node 0 to x.

A path is alternating when no two edges in a row have the same color. If no alternating path reaches x, answer[x] is -1. For node 0, the answer is always 0.

An edge can lead from a node back to itself. Two nodes can be joined by more than one edge.

Example 1

Input: n = 5, redEdges = [[0,1],[1,3],[2,4]], blueEdges = [[1,2],[3,4],[0,3]]
Output: [0,1,2,1,3]
Explanation: Node 3 is one blue edge away: 0 → 3.
But 3 → 4 is blue too, so 0 → 3 → 4 doesn't alternate.
The shortest alternating path to node 4 is 0 → 1 → 2 → 4.
Its colors are red, blue, red: 3 edges.

Example 2

Input: n = 4, redEdges = [[0,2],[2,3]], blueEdges = [[3,1]]
Output: [0,-1,1,-1]
Explanation: Node 2 is one red edge away: 0 → 2.
The next edge must be blue, but node 2 has no blue edge out.
So nodes 1 and 3 are never reached. Both get -1.

Example 3

Input: n = 3, redEdges = [[0,2],[2,1]], blueEdges = [[2,2]]
Output: [0,3,1]
Explanation: The blue loop at node 2 lets the color switch.
So node 1 is 3 edges away:
0 → 2 (red),
2 → 2 (blue),
2 → 1 (red).

Constraints

• 1 to 100 nodes.
• Up to 400 red edges and up to 400 blue edges.
• Both ends of every edge are nodes from 0 to n - 1.