Problem Statement

There is a simple connected undirected graph with $N+1$ vertices and $M$ edges. Vertices $1$ through $N$ are "spectator" vertices, and vertex $N+1$ is the "tower" vertex. The $j$-th edge connects vertex $U_j$ and vertex $V_j$ bidirectionally.

Spectator vertex $i$ has a height $H_i$.

You decide the height $X$ of the tower.

A spectator vertex $v$ is called a "good" vertex if there exist a positive integer $n$ and a vertex sequence $A=(a_1,a_2,\ldots,a_n)$ satisfying the following conditions.

1. $a_1=N+1,a_n=v$
2. $1 \leq a_i \leq N$ for $i \neq 1$
   • All vertices other than $a_1$ are "spectator" vertices
3. Adjacent vertices in the vertex sequence are connected by an edge.
4. For any $1 < i < j \leq n$, the inequality $\frac{H_{a_i}-X}{i-1} \le \frac{H_{a_j}-X}{j-1}$ holds.
   • The "tower" can be seen from any vertex $j$ in the sequence

Note that the same vertex may appear multiple times in the vertex sequence.

Find the minimum non-negative integer $X$ such that all spectator vertices are "good" vertices. It can be proved that such an $X$ exists.

You are given $T$ test cases; solve each of them.

Constraints

• All input values are integers
• $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)$
• The graph is a simple connected undirected graph
• The sum of $N$ in a single input file is at most $3 \times 10^4$
• The sum of $M$ in a single input file is at most $3 \times 10^4$

Input

The input is given from standard input in the following format. Here, $\mathrm{case}_i$ denotes the $i$-th test case.

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

Each test case is given in the following format.

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

Output

Print $T$ lines. The $i$-th line should contain the answer $X$ for the $i$-th test case.

Sample

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