406815: GYM102565 D Galleries

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

D. Galleriestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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).

Input

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.

Output

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.

ExampleInput
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
Output
911708498 517439869 517439869 517439869 517439869 

加入题单

上一题 下一题 算法标签: