You are given a connected graph consisting of \(N\) vertices and \(M\) bidirectional edges. You are also given an array \(A\) of length \(X\) and an array \(B\) of length \(Y\).
The time to reach a vertex \(V\) from an array of vertices \(S\) is defined as the minimum of the shortest distance between \(U\) and \(V\) for all \(U\) in \(S\).
The cost of an array of vertices \(S\) is defined as the sum of the time to reach vertex \(V\) from \(S\) for all \(V\) in \(B\).
Find the last index of the smallest prefix of \(A\) having the minimum cost.
Input Format:
- The first line of input contains a single integer \(T\), denoting the number of test cases.
- The first line of each test case contains two integers \(N\) and \(M\), denoting the number of vertices and the number of initial edges respectively.
- The following \(M\) lines contain 2 integers \(u\) and \(v\), denoting a bidirectional edge between vertex \(u\) and vertex \(v\).
- The next line contains \(X\) and \(Y\), denoting the length of the arrays \(A\) and \(B\) respectively.
- The next line contains \(X\) integers, denoting the elements of array \(A\).
- The last line contains \(Y\) integers, denoting the elements of array \(B\).
Output Format:
For each test case, print the last index of the smallest prefix of \(A\) having the minimum cost.
Constraints:
\(1 <= T <= 10\)
\(1 <= N <= 10^5\)
\(N - 1 <= M <= 10^5\)
\(0 <= u, v < N\)
\(1 <= X, Y <= N\)
\(0 <= A[ i ], B[ i ] < N\)
First test case:-
The cost of \([4]\) is \(dist(4, 0) + dist(4, 5) + dist(4, 2) = 3 + 1 + 1 = 5\).
The cost of \([4,2]\) is \(min(dist(4, 0), dist(2, 0)) + min(dist(4, 5), dist(2, 5)) + min(dist(4, 2), dist(2, 2)) = 2 + 1 + 0 = 3\).
Similarly, the cost of \([4,2,1]\) is \(1 + 1 + 0 = 2\).
Therefore the minimum cost is \(2\) and the last index of the smallest prefix of \(A\) having the minimum cost is \(2\).
Hence, the answer is \(2\).
Second test case:-
The cost of \([1]\) is \(1\).
The cost of \([1,2]\) is also \(1\).
Therefore the minimum cost is \(1\) and the last index of the smallest prefix of \(A\) having the minimum cost is \(0\).
Hence, the answer is \(0\).
Third test case:-
Since, \(B\) consists of only one vertex \(3\), the cost of an array of vertices is just the time to reach \(3\) from the array of vertices.
The cost of \([0]\) is \(2\).
The cost of \([0,1]\) is \(1\).
The cost of \([0,1,2]\) is \(1\).
Therefore the smallest prefix of \(A\) having the minimum cost ends at index \(1\).
Hence, the answer is \(1\).
