你正在为一位来自荷兰的朋友设计一次峰区（Peak District）丘陵之旅。徒步路线将从当地著名的景点“丘陵 1”出发，前往世界闻名的景点“丘陵 2”。

为了让这位朋友有宾至如归的感觉，你希望最小化徒步过程中经过的最高丘陵和最低丘陵之间的高度差。

给定一个包含当地景点及它们之间路径的图，请找到一条这样最平坦的路线。

输入格式

• 第一行包含丘陵的数量 $n$（$2 \le n \le 5\,000$）和连接它们的步道数量 $m$（$1 \le m \le 25\,000$）。
• 第二行包含 $n$ 个整数 $h_1 \dots h_n$（$0 \le h_i \le 10^6$），表示丘陵 1 到 $n$ 的高度（单位：米）。
• 接下来的 $m$ 行，每行包含两个整数 $a$ 和 $b$（$1 \le a, b \le n$），表示丘陵 $a$ 和 $b$ 之间存在一条双向路径。

保证丘陵 1 和丘陵 2 之间存在一条路径（直接或间接）。

输出格式

输出在丘陵 1 和丘陵 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