시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB5231519222.604%

문제

석환나라에는 조승현이라는 이름을 가진 사람이 두 명이 있다. 헷갈리니까 한 명은 조승현13 이라 하고 한 명은 조승현16 이라 하자. 이 둘은 원래 서로의 존재를 모르고 있다가 얼마전에 뉴스를 보고 알게 되었다. 자신과 같은 이름을 가진 사람이 존재한다는 것이 너무 신기했던 그 둘은 연락처를 알아내서 서로 연락하는 사이가 되었다.

어느 날 그 들은 상대방이 사는 도시에 대해 궁금해졌다. 전화로 서로의 도시에 대해 설명해주다가 지친 그 들은 결국 상대방의 도시에 여행을 가기로 결정했다.

석환나라는 N 개의 도시로 이루어져 있고 도시마다 번호가 1부터 N 까지 붙어있다. 그 사이에 도시들을 연결하는 도로 M 개가 있다. 하나의 도로는 도시 두개를 연결하고 그 사이를 양방향으로 다닐 수 있게 한다. 그리고 임의의 한 도시에서 출발하여 도로를 적당히 거쳐가면 다른 모든 도시에 도착할 수 있음이 보장되어있다.

현재 조승현13은 S 번 도시에 있고 조승현16은 E 번 도시에 살고있다. 이 둘은 상대방에게 자신의 도시로 가는 길을 설명해주기 위해 전화로 연락을 유지하면서 다음과 같은 방법으로 여행한다.

  1. 0일차에 조승현13은 S 번 도시에, 조승현16은 E 번 도시에 있다.
  2. i일차 (i ≥ 0)의 아침에 둘은 전화로 연락하여 오늘 누가 움직일지 결정한다. 하루에 둘 중 한 명만 움직일 수 있다.
  3. 이동하기로 결정된 사람은 현재 위치한 도시에 연결된 도로 중 하나를 골라 그 도로를 따라 이동하고, 반대편 도시에 도착하면 이동을 마친다. 이 과정은 석양이 지기 전에 항상 완료된다.
  4. i일차의 석양이 진 후에 둘은 다시 전화로 연락하여 서로의 생사를 확인한다.
  5. 생사를 확인한 직후에 조승현13이 E번 도시에, 조승현16이 S번 도시에 있는 상태라면 여행을 종료한다. 그렇지 않다면, 숙소에서 자고 일어난 후 2번 과정으로 돌아가 반복한다.

전화로 연락하기 위해서는 각자 갖고 있는 전화기가 일정 수준 이상의 무선 신호 출력을 낼 수 있어야 한다. 각 도시 i 마다 무선 신호가 잘 퍼지는지 아닌지를 나타내는 양의 정수 Ci 가 있을 때, 두 도시 a, b 사이에서 전화를 하려면 전화기가 Ca × Cb 이상의 출력을 낼 수 있어야 한다. 이 법칙은 이상한 일이지만 두 명이 같은 도시 안에 있어도 여전히 적용된다.

두 조승현은 여행을 시작하기전에 똑같은 전화기를 하나씩 사서 여행이 끝날 때 까지 그 전화기만 사용할 것이다. 전화기의 가격은 전화기가 낼 수 있는 출력에 비례하기 때문에, 어떻게 여행하느냐에 따라 필요한 전화기의 가격이 변한다. SE 가 주어졌을 때, 여행을 무사히 마치기 위해 필요한 전화기의 출력의 최솟값을 구해서 두 조승현을 만족시켜주자.

입력

주의 : 이 문제의 입력은 하나의 테스트 케이스로 구성되어 있다.

첫 번째 줄에 도시의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 3, 000)이 주어진다. 두 번째 줄에 N 개의 정수가 주어진다. i번째 정수는 Ci (1 ≤ Ci ≤ 40, 000) 를 나타내며 이것은 i번 도시의 무선 신호 상수를 나타낸다.

이후로 M 개의 줄에 걸쳐 2개의 정수 a, b (1 ≤ a, bN, a ≠ b) 가 공백으로 구분되어 주어지는데, 이것은 도시 a와 도시 b 사이를 잇는 도로가 존재함을 뜻한다.

그 다음 줄에 질문의 수 Q (1 ≤ QnC2) 가 주어진다. 이후로 Q 개의 줄에 걸쳐 2개의 정수 S, E (1 ≤ S, EN, SE) 가 공백으로 구분되어 주어지는데, 이것은 처음에 조승현13이 S 번 도시에 있고 조승현16이 E 번 도시에 있을 때의 상황을 뜻하는 것이다.

출력

Q 개의 줄에 각 질문에 대해 여행을 성공적으로 마치기 위해 필요한 전화기의 출력의 최솟값을 구하여 출력한다.

예제 입력 1

5 5
5 1 3 100 12
1 2
2 3
3 1
4 3
4 5
3
1 2
2 3
5 3

예제 출력 1

5
3
100