Xiaobai has $n$ watermelons (it is guaranteed that $n$ is odd), and each watermelon has a weight $a_i$. She has established $m$ undirected edges between these $n$ watermelons such that there is at least one path between any two watermelons.

Xiaobai can now choose three watermelons to merge. Specifically, she chooses three distinct watermelons $x, y, z$ such that there is an undirected edge between $x$ and $y$, and an undirected edge between $y$ and $z$. She obtains a new watermelon $w$ with weight $a_w = \max(a_y, \min(a_x, a_z))$. Next, for every watermelon $t$ that has an undirected edge connected to at least one of $x, y,$ or $z$, she creates an undirected edge between $w$ and $t$. Finally, Xiaobai removes the three watermelons $x, y, z$ and all undirected edges that had $x, y,$ or $z$ as an endpoint.

It can be proven that there always exists a sequence of $\frac{n-1}{2}$ operations such that only one watermelon remains. Xiaobai wants to know the maximum possible weight of the final remaining watermelon.

Input

Read the data from standard input.

The first line contains two non-negative integers $n, m$. It is guaranteed that $1 \le n \le 10^5$, $0 \le m \le 10^5$, and $n$ is odd.

The second line contains $n$ positive integers $a_1, a_2, \dots, a_n$, representing the weight of each watermelon. It is guaranteed that $1 \le a_i \le n$.

The following $m$ lines each contain two positive integers $x, y$, representing an undirected edge $(x, y)$ in the graph. It is guaranteed that $1 \le x, y \le n$ and $x \neq y$.

It is guaranteed that the given undirected graph is connected and contains no multiple edges or self-loops.

Output

Output to standard output.

A single line containing one positive integer, representing the answer.

Examples

Input 1

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

Output 1

2

Input 2

1 0
1

Output 2

1