연결이 되느냐, 안 되느냐, 그것이 문제로다

무방향 그래프가 주어지고, 각 노드에는 양의 정수 값이 하나씩 대응된다. 어떤 임계값이 주어지면 그래프의 노드는 두 그룹으로 나뉜다. 한 그룹은 값이 임계값 이하인 노드로, 다른 그룹은 나머지 노드로 이루어진다. 이제 서로 다른 그룹에 속한 두 노드를 잇는 간선을 모두 제거해서 얻은 부분 그래프를 생각하자. 두 노드 그룹이 모두 비어 있지 않다면, 주어진 그래프가 연결되어 있든 아니든 이 부분 그래프는 연결되어 있지 않다.

그다음 부분 그래프를 연결 상태로 만들기 위해 새 간선을 여러 개 추가하는데, 이 간선들은 서로 다른 그룹의 노드를 연결해야 하고 각 노드는 새 간선과 최대 한 번만 만날 수 있다. 두 그룹 중 어느 쪽도 비어 있지 않고 새 간선을 몇 개 추가해서 부분 그래프를 연결 상태로 만들 수 있으면 그 임계값을 실현 가능하다고 한다.

최소 실현 가능 임계값을 구하시오.

입력은 다음과 같은 형식의 테스트 케이스 하나로 이루어진다.

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

첫째 줄에는 그래프의 노드 수와 간선 수를 나타내는 두 정수 n (2 ≤ n ≤ 105)과 m (0 ≤ m ≤ min(105, n(n−1)/2))이 주어진다. 노드에는 1부터 n까지 번호가 붙는다. 둘째 줄에는 n개의 정수 li (1 ≤ li ≤ 109)가 주어지는데, 노드 i에 대응하는 값이 li라는 뜻이다. 이어지는 m개의 줄에는 각각 두 정수 xj와 yj (1 ≤ xj < yj ≤ n)가 주어지는데, 노드 xj와 yj를 잇는 간선이 있다는 뜻이다. 두 노드 사이에는 간선이 최대 하나만 존재한다.

최소 실현 가능 임계값을 출력한다. 실현 가능한 임계값이 하나도 없으면 -1을 출력한다.