F. Fell Walking
time limit per test
3.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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.

Input

  • 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

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

Examples
Input
5 6
1 2 3 4 5
1 3
1 5
2 4
3 4
4 5
5 2
Output
3
Input
6 6
50 50 5 50 30 70
6 5
3 1
1 6
1 3
5 2
4 2
Output
40