#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <cstring>
#include <iostream>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <complex>

#define mp(a, b) make_pair((a), (b))
#define pb(a) push_back((a))
#define pf(a) push_front((a))
#define rb() pop_back()
#define rf() pop_front()
#define sz(a) ((int)a.size())

using namespace std;

typedef long long lld;
typedef pair<int, int> pii;
typedef pair<lld, lld> pll;
typedef pair<lld, int> pli;
typedef pair<int, lld> pil;
typedef vector<vector<int>> Matrix;
typedef vector<vector<int>> Adj;
typedef vector<int> Row;
typedef complex<double> Complex;
typedef vector<Complex> Vcomplex;

const int MOD = 1e9 + 7;
const int INF = 1e9;
const lld LINF = 1e18;
const double FINF = 1e15;
const double EPS = 1e-9;
const double PI = 2.0 * acos(0.0);

const int M = 19;

int n, m;
int c[505];
vector<int> g[505];
vector<int> g2[250005];
int par[250005][25];
int p[250005];
int cost[250005][25];
int depth[250005];

inline int encode(int i, int j) {
  return i * n + j;
}

int max_cost(int u, int v) {
  if (depth[u] < depth[v]) swap(u, v);
  int ret = 0;
  int d = depth[u] - depth[v];
  for (int i = 0; i < M; ++i) {
    if (d&1<<i) {
      ret = max(ret, cost[u][i]);
      u = par[u][i];
    }
  }

  if (u == v) return ret;
  for (int i = M - 1; i >= 0; --i) {
    if (par[u][i] != par[v][i]) {
      ret = max(ret, cost[u][i]);
      ret = max(ret, cost[v][i]);
      u = par[u][i];
      v = par[v][i];
    }
  }
  return max(ret, max(cost[u][0], cost[v][0]));
}

void dfs(int cur) {
  for (auto nxt : g2[cur]) {
    if (nxt != par[cur][0]) {
      depth[nxt] = depth[cur] + 1;
      par[nxt][0] = cur;
      cost[nxt][0] = max(cost[nxt][0], c[cur/n] * c[cur%n]);
      dfs(nxt);
    }
  }
}

int f(int x) {
  return p[x] = (x == p[x] ? x : f(p[x]));
}

int main() {
  scanf("%d %d", &n, &m);
  for (int i = 0; i < n; ++i) scanf("%d", &c[i]);
  for (int i = 0; i < m; ++i) {
    int u, v;
    scanf("%d %d", &u, &v);
    --u, --v;
    g[u].pb(v);
    g[v].pb(u);
  }
  vector<pii> V;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      cost[encode(i, j)][0] = c[i] * c[j];
      V.emplace_back(c[i] * c[j], encode(i, j));
    }
  }
  for (int i = 0; i < n * n; ++i) p[i] = i;
  sort(V.begin(), V.end());
  for (pii vv : V) {
    int u = vv.second / n;
    int v = vv.second % n;
    for (int nxt : g[u]) {
      int en = encode(nxt, v);
      if (c[nxt] * c[v] <= c[u] * c[v]) {
        int cp = f(vv.second);
        int np = f(en);
        if (cp != np) {
          p[cp] = np;
          g2[vv.second].pb(en);
          g2[en].pb(vv.second);
        }
      }
    }
    for (int nxt : g[v]) {
      int en = encode(u, nxt);
      if (c[u] * c[nxt] <= c[u] * c[v]) {
        int cp = f(vv.second);
        int np = f(en);
        if (cp != np) {
          p[cp] = np;
          g2[vv.second].pb(en);
          g2[en].pb(vv.second);
        }
      }
    }
  }
  dfs(0);
  for (int i = 0; i < M - 1; ++i) {
    for (int j = 0; j < n * n; ++j) {
      par[j][i+1] = par[par[j][i]][i];
      cost[j][i+1] = max(cost[j][i], cost[par[j][i]][i]);
    }
  }
  int q;
  scanf("%d", &q);
  for (int i = 0; i < q; ++i) {
    int u, v;
    scanf("%d %d", &u, &v);
    --u, --v;
    printf("%d\n", max_cost(encode(u, v), encode(v, u)));
  }
}