問題文

$N+1$ 頂点 $M$ 辺の単純連結無向グラフがあります。 頂点 $1$ から頂点 $N$ は「観客」の頂点であり、頂点 $N+1$ は「塔」の頂点です。 $j$ 番目の辺は頂点 $U_j$ と頂点 $V_j$ を双方向に結びます。

観客の頂点 $i$ には高さ $H_i$ が設定されています。

あなたは塔の高さ $X$ を決定します。

観客の頂点 $v$ が「良い」頂点であるとは、正整数 $n$ と次の条件を満たす頂点列 $A=(a_1,a_2,\ldots,a_n)$ が存在することを言います。

1. $a_1=N+1,a_n=v$
2. $i \neq 1$ において $1 \leq a_i \leq N$
   • $a_1$ 以外はすべて「観客」の頂点である
3. 頂点列の隣接する頂点同士は辺で結ばれている。
4. 任意の $1 < i < j \leq n$ について、不等式$\frac{H_{a_i}-X}{i-1} \le \frac{H_{a_j}-X}{j-1}$が成り立つ。
   • 列中の任意の頂点 $j$ から「塔」を見ることができる

頂点列に同じ頂点が複数回登場しても問題ないことに注意してください。

すべての観客の頂点が「良い」頂点となるような最小の非負整数 $X$ を求めてください。この $X$ の存在は証明できます。

$T$ 個のテストケースが与えられるので、それぞれについて解いてください。

制約

• 入力はすべて整数
• $1 \le T \leq 1000$
• $1 \leq N \leq 2000$
• $N \leq M \leq 2000$
• $1 \leq H_i \leq 10^9 \ (1 \leq i \leq N)$
• $1 \leq U_j < V_j \leq N+1 \ (1 \leq j \leq M)$
• グラフは単純連結無向グラフである
• 1つの入力ファイルにおいて $N$ の総和は $3 \times 10^4$ 以下
• 1つの入力ファイルにおいて $M$ の総和は $3 \times 10^4$ 以下

入力

入力は以下の形式で標準入力から与えられる。ここで $\mathrm{case}_i$ は $i$ 番目のテストケースを意味する。

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

各テストケースは次の形式で与えられる。

$N$ $M$
$H_1$ $H_2$ $\ldots$ $H_N$
$U_1$ $V_1$
$\vdots$
$U_M$ $V_M$

出力

$T$ 行出力せよ。 $i$ 行目には $i$ 番目のテストケースに対する答え $X$ を出力せよ。

サンプル

2
3 3
4 3 6
1 2
2 4
3 4
4 4
9 8 1 1
1 2
2 3
3 4
4 5

2
1