Ninja And Trains

Ninja is given a few cities and few connected Trains. Each city has a specific size. Now due to bad weather, trains from certain cities get canceled. Given a value X, if the size of the city is less than X, then all incoming and outgoing trains from the station get canceled. Now Ninja’s task is to determine the maximum threshold value X such that trains from cities with a size less than X gets canceled, then there should exist a reachable component of cities in the network of size at least K. A subcomponent of the city network is considered to be a reachable component if all the cities in that network are connected, which implies all the trains are available from each other via direct or connecting trains.

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 ‘N’, denoting the number of cities, ‘M’ denoting the number of trains, and ‘K’ denoting the size of the connected network of cities.

The second line of each test case contains 'N' space-separated integers denoting the value associated with the i-th city.

The next 'M' lines of each test case contains ‘M’ pairs (u, v), denoting a train available from city u to city v.

Output Format :

The first and only line of each test case contains the maximum threshold value X, if the maximum threshold value is infinite the return 10 ^ 9. If there is no connected network of cities of size at least K, then return -1.

Note:

You are not required to print the expected output; it has already been taken care of. Just implement the function. 

Constraints:

1 <= T <= 5 
1 <= k <= N <= 10^5
1 <= M <= 10^5
1 <= value of nodes <= 10 ^ 9

Time limit: 2 second