406815: GYM102565 D Galleries

You own one of the biggest art museums in the country!

The museum consists of $$$1 \leq N \leq 10^5$$$ galleries and $$$1 \leq M \leq 2*10^5$$$ corridors. You may walk from a gallery to another one if there is a corridor in between them.

Each gallery has associated to it a value $$$1 \leq V_i \leq 10^9$$$. This week you decide to host a mega promotion: each visitor must only pay a cost equal to the biggest value among the galleries he decides to visit!

Now, in order to see how much money you might lose, you ask yourself $$$1 \leq Q \leq 10^5$$$ questions of type $$$X$$$, $$$K$$$ and you want to know, for a person that enters the museum through gallery $$$X$$$, what is the minimum cost of a pass he must purchase in order to visit at least $$$K$$$ distinct galleries(including $$$X$$$). It is guaranteed that for each query $$$1 \leq X \leq N$$$ and $$$1 \leq K \leq N$$$.

You may walk from a gallery to another only if there exists a corridor in between the two. You may not enter a gallery without visiting it and you can pass through the same one multiple times(though it only counts towards the answer once). You also have to stay inside of the galleries at all times(meaning you can't exit the museum and enter through another gallery).

The first line of input consists of 2 numbers: $$$N$$$ and $$$M$$$, the number of galleries and corridors respectively.

The next lines contains $$$N$$$ integers, the values of the galleries.

The following $$$M$$$ lines each contain 2 integers $$$X$$$ and $$$Y$$$ describing an undirected corridor between the 2 galleries.

The next line contains one number $$$Q$$$, the number of questions.

Each of the next $$$Q$$$ lines describes one of the questions.

Your output should consist of $$$Q$$$ lines, the answer to the questions in the order they appear in the input. On each such line, there should be one integer representing the minimum cost of a pass.

It is guaranteed that you may reach any gallery from every other one.

10 14
517439869 911708498 120170079 452675108 704687086 127806914 462723433 303807567 59344841 231845950
1 3
7 10
6 1
2 3
3 4
10 6
8 4
5 1
6 1
1 5
6 9
6 5
9 5
5 1
5
4 10
3 5
4 5
8 8
3 6

911708498 517439869 517439869 517439869 517439869