题目描述

An undirected graph is given, each of its nodes associated with a positive integer value. Given a threshold, nodes of the graph are divided into two groups: one consisting of the nodes with values less than or equal to the threshold, and the other consisting of the rest of the nodes. Now, consider a subgraph of the original graph obtained by removing all the edges connecting two nodes belonging to different groups. When both of the node groups are non-empty, the resultant subgraph is disconnected, whether or not the given graph is connected.

Then a number of new edges are added to the subgraph to make it connected, but these edges must connect nodes in different groups, and each node can be incident with at most one new edge. The threshold is called feasible if neither of the groups is empty and the subgraph can be made connected by adding some new edges.

Your task is to find the minimum feasible threshold.

输入格式

The input consists of a single test case of the following format.

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

The first line contains two integers $n$ ($2 \le n \le 10^5$) and $m$ ($0 \le m \le \min(10^5, \frac{n(n-1)}{2})$), the numbers of the nodes and the edges, respectively, of the graph. Nodes are numbered 1 through $n$. The second line contains $n$ integers $l_i$ ($1 \le l_i \le 10^9$), meaning that the value associated with the node $i$ is $l_i$. Each of the following $m$ lines contains two integers $x_j$ and $y_j$ ($1 \le x_j < y_j \le n$), meaning that an edge connects the nodes $x_j$ and $y_j$. At most one edge exists between any two nodes.

输出格式

Output the minimum feasible threshold value. Output $-1$ if no threshold values are feasible.

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