# Shortest alternate colored path

Moderate
0/80
Average time to solve is 20m
Contributed by

## Problem statement

Consider a directed graph of ‘N’ nodes where each node is labeled from ‘0’ to ‘N - 1’. Each edge of the graph is either ‘red’ or ‘blue’ colored. The graph may contain self-edges or parallel edges. You are given two arrays, ‘redEdges’ and ‘blueEdges’, whose each element is of the form [i, j], denoting an edge from node ‘i’ to node ‘j’ of the respective color.

Your task is to compute an array ‘answer’ of size ‘N’, where ‘answer[i]’ stores the length of the shortest path from node ‘0’ to node ‘i’ such that the edges along the path have alternate colors. If there is no such path from node ‘0’ to ‘i’, then ‘answer[i] = -1’.

Example:
``````N = 4, redEdges = [[0, 1], [2, 3]], blueEdges = [[1, 2], [1, 3]]
``````

``````The shortest paths for each node from node ‘0’ are:
1: 0->1         Length: 1
2: 0->1->2      Length: 2
3: 0->1->3      Length: 2
So, the ‘answer’ array will be: [0, 1, 2, 2].
``````
Note:
``````1. The given graph could be a disconnected graph.

2. Any two nodes ‘i’ and ‘j’ can have at most one red edge from ‘i’ to ‘j’ and at most one blue edge from ‘i’ to ‘j’.
``````
Detailed explanation ( Input/output format, Notes, Images )
Constraints:
``````1 <= T <= 100
1 <= N <= 200
0 <= rlen + blen <= 1000

Where ‘T’ is the number of test cases, ‘N’ is the number of nodes in the graph, ‘rlen’ is the size of array ‘redEdges’, and ‘blen’ is the size of array ‘blueEdges’.

Time limit: 1 second
``````

#### Sample input 1:

``````2
4 2 2
0 1
1 3
1 1
1 2
4 2 2
0 1
1 3
0 2
2 3
``````

#### Sample output 1:

``````0 1 2 3
0 1 1 -1
``````

#### Explanation of sample input 1:

``````Test Case 1:

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

``````The shortest paths for each node from node ‘0’ are:
1: 0->1          Length: 1
2: 0->1->2      Length: 2
3: 0->1->1->3   Length: 3
So, the ‘answer’ array will be: [0, 1, 2, 3].

Test Case 2:

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

``````The shortest paths for each node from node ‘0’ are:
1: 0->1     Length: 1
2: 0->2     Length: 1
3: No valid path available.
So, the ‘answer’ array will be: [0, 1, 1, -1].
``````

#### Sample input 2:

``````2
3 1 1
2 1
1 0
3 1 2
1 0
0 1
0 2
``````

#### Sample output 2:

``````0 -1 -1
0 1 1
``````
Console