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

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

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

输入格式

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

$n$ $m$ $l_1 \dots l_n$ $x_1$ $y_1$ $\vdots$ $x_m$ $y_m$

第一行包含两个整数 $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$ 之间有一条边。任意两个节点之间最多存在一条边。

输出格式

输出最小的可行阈值。如果不存在可行的阈值，则输出 $-1$。

样例

样例输入 1

4 2
10 20 30 40
1 2
3 4

样例输出 1

20

样例输入 2

2 1
3 5
1 2

样例输出 2

3

样例输入 3

3 0
9 2 8

样例输出 3

-1

样例输入 4

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

样例输出 4

-1

样例输入 5

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

样例输出 5

2