# Minimum time

Moderate
0/80
Average time to solve is 15m

## Problem statement

You are given an arbitrary graph consisting of V vertices and E edges, a source node (S) and a destination node (D). Every node of the graph has a colour (Red, Blue or Green) associated with it. The cost of travelling from one node to some adjacent node takes 1 second. If you stop at a node for 1 second, you will get a colour ball of the colour of the current node.

You have to find the minimum time taken in order to reach from source to destination node ensuring that the number of balls of each colour is equal and non-zero. The source and destination nodes will always be in different colours.

Note:

``````1. The given graph is never empty and consists of at least 3 nodes with the colour Red, Green and Blue each.
2. There are no self-loops(an edge connecting a node to itself) in a graph.
3. There are no parallel edges i.e no two nodes are directly connected by more than 1 edge in the given graph.
4. The nodes in the graph are numbered from 1 to V.
5. All the edges in the graph are bidirectional.
6. You can stay at one node for more than 1 second as well, but every second you stay there you will get an additional colour ball of the colour of that node.
7. Number of edges(E) in the graph is always equal to V-1.
8. You can also collect the ball from the destination and the source node itself. Also if you reach the destination without having an equal number of balls for each colour, the time calculated would not be valid.
``````
Detailed explanation ( Input/output format, Notes, Images )
Constraints:
``````1 <= T <= 10
3 <= V <= 5000
E = V - 1
1 <= a,b <= V

Time Limit: 1 sec
``````
##### Sample Input 1:
``````2
6 5
1 0 2 1 2 0
1 2
1 3
3 4
3 5
2 6
6 5
5 4
0 0 1 2 1
1 2
2 3
3 4
3 5
1 5
``````
##### Sample Output 1:
``````7
8
``````
##### Explanation for Sample Input 1:
``````For the first test case of sample input 2, Source Node, S = 6 and Destination Node, D = 5.
The tree depicted is as follows:
``````

``````For the second test case of sample input 2, Source Node, S = 1 and Destination Node, D = 5.
The tree depicted is as follows:
``````

##### Sample Input 2:
``````2
5 4
1 0 2 0 0
3 1
4 2
2 3
5 3
2 1
4 3
0 0 2 1
3 2
3 1
3 4
4 3
``````
##### Sample Output 2:
``````5
6
``````
Console