시간 제한메모리 제한제출정답맞힌 사람정답 비율
3.5 초 2048 MB148857.143%

문제

You are creating a tour of the Peak District hills for a friend visiting from the Netherlands. The walk will go from the locally famous viewpoint "Hill 1" to the world-famous viewpoint "Hill 2".

To make this friend feel at home, you want to minimise the difference in height between the highest and lowest hills of the walk.

Given a graph of the local points of interest and paths between them, find such an optimally-flat route.

입력

  • One line containing the number of hills, $n$ ($2 \le n \le 5,000$), and the number of trails connecting them, $m$ ($1 \le m \le 25,000$).
  • One line containing $n$ integers $h_1 \ldots h_n$ ($0 \le h \le 10^6$), the heights in metres of the hills from $1$ to $n$.
  • $m$ further lines, the $i$-th of which contains two integers $a$ and $b$ ($1 \le a, b \le n$) indicating that there is a bi-directional path between hills $a$ and $b$.

It is guaranteed that there is a path (direct or indirect) between hills $1$ and $2$.

출력

Output the minimum possible distance between the maximum and minimum heights of hills encountered on a walk between hills $1$ and $2$.

예제 입력 1

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

예제 출력 1

3

예제 입력 2

6 6
50 50 5 50 30 70
6 5
3 1
1 6
1 3
5 2
4 2

예제 출력 2

40