"""

i >= 1

(u, v) について、
- h[u] = h[v] <= x のとき (u, v) と (v, u) が存在
- h[u] = h[v] > x のとき どちらも存在しない

- h[u] < h[v] のとき、
i >= (h[u] - x) / (h[v] - h[u]) のとき、(u, v) が存在
    - h[u] - x <= 0 のとき、常に(u, v) が存在

i <= (x - h[v]) / (h[v] - h[u]) のとき、(v, u) が存在
    - x - h[v] <= 0 のとき、常に(v, u) は存在しない

- h[u] < h[v] とする
- x < h[u] のとき (u, v) は i >= d(u, v) のとき存在、(v, u) は存在しない
- x > h[v] のとき (v, u) は i <= d(u, v) のとき存在、(u, v) 常に存在
- h[u] <= x <= h[v] のとき、(u, v) は常に存在、(v, u) は存在しない

2 (n + 1) 頂点で考える
(頂点、パリティ)で考えたときに、

h[i] <= x のとき、 

h[i] > x になったら、常に h[i] は狭義単調増加、逆戻りもできない

h[i] <= x のときに、どれだけ回数を稼げるかになる。

n, a[1], a[2], ..., a[s], a[s+1], ...

h[a[i]] <= x (i <= s)
x < h[a[s+1]] < h[a[s+2]] < ...

各h[i] <= x となる頂点について、訪れることが出来る最大の時刻を求める

d(u, v) < inf のとき、 d(v, u) = inf が成り立つ

(2 * (n + 1) 頂点で考える)
回数の稼ぎ方として、長さ 2 より大きいループはいらない
(なぜなら、ループの最後に現れた頂点との往復に置き換えれるから)
また、往復する辺は高々 1個だけでいい。

よって、ある辺で、往復したときの最大時刻を求めて

"""


from collections import deque

def solve(n, h, g):
    inf = 10 ** 18
    idx = sorted(range(n), key=lambda x: h[x])
    h = h + [-1]
    def check(x):
        h[n] = x
        N = 2 * (n + 1)
        """
        h[i] <= x の頂点の最短距離
        """
        dist = [-1] * N
        from collections import deque
        dq = deque()
        for i in g[n]:
            if h[i] <= x:
                dist[i * 2 + 1] = 1
                dq.append(i * 2 + 1)
        dist[n * 2] = 0

        while dq:
            ui, uj = divmod(dq.popleft(), 2)

            vj = uj ^ 1
            for vi in g[ui]:
                if vi == n:
                    continue
                if h[vi] <= x:
                    if h[ui] == h[vi]:
                        if dist[vi * 2 + vj] == -1:
                            dist[vi * 2 + vj] = dist[ui * 2 + uj] + 1
                            dq.append(vi * 2 + vj)
                    elif h[ui] < h[vi]:
                        if dist[vi * 2 + vj] == -1:
                            dist[vi * 2 + vj] = dist[ui * 2 + uj] + 1
                            dq.append(vi * 2 + vj)
                    else:
                        L = (x - h[ui]) // (h[ui] - h[vi])
                        # print(L)
                        if L >= dist[ui * 2 + uj]:
                            if dist[vi * 2 + vj] == -1:
                                dist[vi * 2 + vj] = dist[ui * 2 + uj] + 1
                                dq.append(vi * 2 + vj)
        
        final = dist[:]
        for _ in range(2):# 二回やることで、もとに戻るのも考慮
            for ui in range(n):
                if h[ui] > x:
                    continue
                for uj in range(2):
                    if dist[ui * 2 + uj] == -1:
                        continue
                    for vi in g[ui]:
                        if h[vi] > x:
                            continue
                        if vi == n:
                            continue
                        vj = uj ^ 1
                        # ui -> vi にできるだけ往復する
                        d1 = inf
                        d2 = inf
                        if h[ui] < h[vi]:
                            d2 = (x - h[vi]) // (h[vi] - h[ui])
                        elif h[ui] > h[vi]:
                            d1 = (x - h[ui]) // (h[ui] - h[vi])
                        
                        if d1 >= dist[ui * 2 + uj]:
                            final[vi * 2 + vj] = max(final[vi * 2 + vj], dist[ui * 2 + uj] + 1)

                        if d2 == inf and d1 == inf:
                            k = inf
                        else:
                            k = min((d1 - uj) // 2, (d2 - uj + 1) // 2)
                        
                        if uj + 2 * k >= dist[ui * 2 + uj]:
                            final[vi * 2 + vj] = max(final[vi * 2 + vj], min(uj + 2 * k + 1, inf))
                    

        def transition(ui):
            for uj in range(2):
                if final[ui * 2 + uj] == -1:
                    continue
                for vi in g[ui]:
                    if vi == n:
                        continue
                    # if h[vi] <= x:
                    #     continue
                    if h[ui] >= h[vi]:
                        continue
                    vj = uj ^ 1
                    d = (h[ui] - x - 1) // (h[vi] - h[ui]) + 1
                    if final[ui * 2 + uj] != -1 and final[ui * 2 + uj] >= d:
                        # print((ui+1, uj), "->", (vi+1, vj), d)
                        final[vi * 2 + vj] = max(final[vi * 2 + vj], min(inf, final[ui * 2 + uj] + 1))
                   
        for ui in idx:
            if h[ui] > x:
                break
            transition(ui)
        transition(n)
        for ui in idx:
            if h[ui] <= x:
                continue
            transition(ui)
        
        return all(final[i * 2] >= 0 or final[i * 2 + 1] >= 0 for i in range(n))

    ok = max(h) * n
    ng = -1

    while ok - ng > 1:
        mid = (ok + ng) // 2
        res = check(mid)
        if res:
            ok = mid
        else:
            ng = mid
    return ok

for _ in range(int(input())):
    n, m = map(int, input().split())
    h = list(map(int, input().split()))
    g = [[] for _ in range(n + 1)]
    for _ in range(m):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        g[u].append(v)
        g[v].append(u)
    print(solve(n, h, g))