You are given a connected graph consisting of vertices and bidirectional edges. You are also given an array of length and an array of length .
The time to reach a vertex from an array of vertices is defined as the minimum of the shortest distance between and for all in .
The cost of an array of vertices is defined as the sum of the time to reach vertex from for all in .
Find the last index of the smallest prefix of having the minimum cost.
Input Format:
Output Format:
For each test case, print the last index of the smallest prefix of having the minimum cost.
Constraints:
3 6 5 0 1 1 2 2 4 4 3 4 5 3 3 4 2 1 0 5 2 3 3 0 1 1 2 2 0 2 1 1 2 0 4 3 0 1 1 2 1 3 3 1 0 1 2 3
First test case:-
The cost of is .
The cost of is .
Similarly, the cost of is .
Therefore the minimum cost is and the last index of the smallest prefix of having the minimum cost is .
Hence, the answer is .
Second test case:-
The cost of is .
The cost of is also .
Therefore the minimum cost is and the last index of the smallest prefix of having the minimum cost is .
Hence, the answer is .
Third test case:-
Since, consists of only one vertex , the cost of an array of vertices is just the time to reach from the array of vertices.
The cost of is .
The cost of is .
The cost of is .
Therefore the smallest prefix of having the minimum cost ends at index .
Hence, the answer is .