0

# Ninja And Trains

Difficulty: HARD
Contributed By
Avg. time to solve
60 min
Success Rate
40%

Problem Statement

#### 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
``````
##### Sample Input 1:
``````2
6 7 3
100 150 68 138 32 22
1 2
2 3
3 4
4 5
5 1
4 6
6 3
4 5 3
100 150 68 62
1 2
3 4
2 3
4 1
3 1
``````
##### Sample Output 1:
``````32
68
``````
##### Explanation for Sample Output 1:
``````In the first test case, we can traverse all the node’s values starting from 150 and set them as ‘X’  and check if we remove it will the remaining nodes form a connected component of size at least K. Here we start from 150 and then go to 32. For X= 32, the required conditions are satisfied. For other values of X greater than 32, the conditions are not satisfied, so we return 32 as our answer.

In the second test case, we traverse all the node’s values starting from 150. We can see that if we remove nodes whose values are less than it, then the connected component of size at least 3 is not maintained. So we further decrease X. Finally we reach the value of X = 68, for which given conditions are satisfied. So we return 68 as our answer.
``````
##### Sample Input 2:
``````2
4 4 2
3 1 4 5
1 2
2 3
3 4
4 1
5 5 3
3 1 4 5 10
1 2
2 3
3 4
4 1
2 5
``````

##### Sample Output 2:

``````1
1
``````
Console