21932번 - 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.

n m
l1 . . . ln
x1 y1
.
.
.
xm ym

The first line contains two integers n (2 ≤ n ≤ 10⁵) and m (0 ≤ m ≤ min(10⁵, 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 ≤ l_i ≤ 10⁹), 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 ≤ x_j < y_j ≤ 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.