14619번 - 섬 여행

취미가 여행이고 특기가 여행인 정우는 이번에는 여러 섬들을 여행해보려고 한다. 정우가 목적지로 잡은 섬은 총 N개이며 N개의 섬들은 M개의 양방향 통행 다리가 이어져 있어서 한 섬에서 다른 섬으로 이동할 수 있는 여러 경로가 존재한다.

정우는 섬의 지도를 보다가 지도에 적힌 섬의 높이를 보고 문득 이런 생각을 하게 된다.

“어떤 섬 A에서 출발하여 K개의 다리를 이동하였을 때, 도착할 수 있는 높이가 가장 낮은 섬의 높이는 무엇일까?”

정우가 궁금해하는 문제를 대신 해결해주자!

입력의 첫째 줄에 N, M(2 ≤ N ≤ 100, 1 ≤ M ≤ 10,000)이 공백으로 구분되어 주어진다.

입력의 둘째 줄에 N개의 섬의 높이 H(0 ≤ H ≤ 10,000)가 공백으로 구분되어 주어진다.

입력의 셋째 줄 부터 M개의 줄에 섬의 연결을 나타내는 정수 X, Y가 공백으로 구분 되어 주어진다.(1 ≤ X, Y ≤ N) 이는 X, Y 두 섬이 양방향 통행 다리로 연결되어 있다는 의미다.

입력의 M+4째 줄에 정우가 궁금해하는 질의의 수 T(1 ≤ T ≤ 10,000)가 주어진다.

다음 T개의 줄에 현재의 위치 A(1 ≤ A ≤ N)와 이동해야 하는 다리의 수 K(1 ≤ K ≤ 500)가 주어진다.

각 질의에 대해서 각 줄 마다 A번 섬에서 정확히 K번 이동하였을 때 도착 가능한 섬들의 높이 중 가장 낮은 섬의 높이를 출력한다.

K번 이동하였을 때 도착 가능한 섬이 없을 경우 -1을 출력한다.