Problem of the day
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].
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’.
The first line of input contains an integer ‘T’ which denotes the number of test cases. Then, the ‘T’ test cases follow.
The first line of each test case contains three space-separated integers ‘N’, ‘rlen’, and ‘blen’ denoting the number of nodes in the graph, the size of array ‘redEdges’, and the size of array ‘blueEdges’.
The next 'rlen' lines of each test case contain two space-separated integers, ‘i’ and ‘j’ denoting a ‘red’ edge from node ‘i’ to node ‘j’.
The next 'blen' lines of each test case contain two space-separated integers, ‘i’ and ‘j’ denoting a ‘blue’ edge from node ‘i’ to node ‘j’.
For every test case, print a single line containing N space-separated integers denoting array ‘answer’, where ‘answer[i]’ contains the valid shortest path length from node ‘0’ to node ‘i’.
The output for each test case will be printed in a separate line.
You do not need to print anything; it has already been taken care of. Just implement the function.
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
2
4 2 2
0 1
1 3
1 1
1 2
4 2 2
0 1
1 3
0 2
2 3
0 1 2 3
0 1 1 -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].
2
3 1 1
2 1
1 0
3 1 2
1 0
0 1
0 2
0 -1 -1
0 1 1