Description

给定一个无向图，其中每个节点都关联一个正整数。给定一个阈值，图的节点被分成两组：一组由值小于或等于该阈值的节点组成，另一组由其余节点组成。现在，考虑原图的一个子图，该子图是通过移除所有连接两个属于不同组的节点的边而得到的。当两个节点组都非空时，无论原图是否连通，得到的子图都是不连通的。

然后，向该子图中添加若干新边以使其连通，但这些新边必须连接不同组中的节点，并且每个节点最多只能与新边中的一条边关联。如果一个阈值满足以下条件，则称其为可行的：两个组均非空，并且可以通过添加一些新边使得子图连通。

你的任务是找出最小的可行阈值。

Input Format

输入包含单个测试用例，格式如下。

$$\begin{aligned} &n \ m \\ &l_1 \ldots l_n \\ &x_1 \ y_1 \\ &\vdots \\ &x_m \ y_m \\ \end{aligned}$$

第一行包含两个整数 $n$ （$2 \le n \le 10^5$）和 $m$ （$0 \le m \le \min(10^5, \frac{n(n-1)}{2})$），分别表示图的节点数和边数。节点编号为 $1$ 到 $n$。第二行包含 $n$ 个整数 $l_i$ （$1 \le l_i \le 10^9$），表示节点 $i$ 关联的值为 $l_i$。接下来的 $m$ 行中，每行包含两个整数 $x_j$ 和 $y_j$ （$1 \le x_j < y_j \le n$），表示节点 $x_j$ 和 $y_j$ 之间有一条边。任意两个节点之间最多存在一条边。

Output Format

输出最小的可行阈值。如果没有可行的阈值，则输出 $-1$。

4 2
10 20 30 40
1 2
3 4

20

2 1
3 5
1 2

3

3 0
9 2 8

-1

4 6
5 5 5 5
1 2
1 3
1 4
2 3
2 4
3 4

-1

7 6
3 1 4 1 5 9 2
2 3
3 5
5 6
1 4
1 7
4 7

2