A warehouse floor has n stations 0 .. n-1 connected by one-way lanes painted red or blue.
red[i] = [u, v] is a red lane from u to v; blue[i] = [u, v] is a blue lane from u to v. A
robot leaving station 0 must alternate colours: after a red lane it must take a blue one and
vice versa. The first lane may be either colour. Lanes may loop back to their own station and may be
repeated.
Return a list steps where steps[i] is the fewest lanes needed to reach station i under this rule,
or -1 if it cannot be reached. steps[0] = 0.
Examples
Input: n = 3, red = [[0,1]], blue = [[1,2]]
Output: [0, 1, 2]
Input: n = 3, red = [[0,1],[1,2]], blue = []
Output: [0, 1, -1]
Explanation: two red lanes in a row are not allowed.
Input: n = 3, red = [[0,1],[1,2]], blue = [[1,1]]
Output: [0, 1, 3]
Explanation: red 0->1, blue 1->1, red 1->2.
Constraints
1 <= n <= 5000,0 <= len(red), len(blue) <= 10**4- Target
O(V + E)time.
Goals
- Expand each node into two states, one per last colour used
- Run BFS on the state graph to get unweighted shortest paths
- Merge the two states back into one answer per node