#214987. [ICPC 2020 Yokohama R] To be Connected, or not to be, that is the Question

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.

The first line contains two integers () and (), the numbers of the nodes and the edges, respectively, of the graph. Nodes are numbered 1 through . The second line contains integers (), meaning that the value associated with the node is . Each of the following lines contains two integers and (), meaning that an edge connects the nodes and . At most one edge exists between any two nodes.

Output the minimum feasible threshold value. Output if no threshold values are feasible.

样例输入 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