Description
Given a directed graph with red and blue edges, find the shortest path to each node using alternating colors from node 0.
Examples
Input:
n=3, redEdges=[[0,1],[1,2]], blueEdges=[]Output:
[0,1,-1]Explanation:
Can't reach node 2 with alternating colors.
Input:
n=4, redEdges=[[0,1],[2,3]], blueEdges=[[1,2],[0,3]]Output:
[0,1,2,1]Explanation:
From node 0: reach node 1 via red edge (distance 1), reach node 2 via red edge to 1 then blue edge to 2 (distance 2), reach node 3 via blue edge (distance 1). All paths maintain alternating colors.
Input:
n=3, redEdges=[[0,1],[0,2]], blueEdges=[[1,0]]Output:
[0,1,1]Explanation:
From node 0: reach node 1 via red edge (distance 1), reach node 2 via red edge (distance 1). Node 2 is unreachable with alternating colors starting with blue, but reachable starting with red.
Constraints
- •
1 ≤ n ≤ 100 - •
0 ≤ redEdges.length, blueEdges.length ≤ 400