Vương quốc Byteland có ~N~ thành phố, được đánh số từ ~1~ đến ~N~. Thành phố thứ ~i~ có độ cao ~H_i~.

Hệ thống giao thông gồm ~M~ con đường hai chiều, bảo đảm từ bất kỳ thành phố nào cũng có thể đi đến bất kỳ thành phố nào khác. Mỗi con đường nối hai thành phố phân biệt.

Đoàn công tác cần đi từ thành phố ~1~ đến thành phố ~N~. Với một hành trình cụ thể, xét chênh lệch độ cao giữa hai thành phố liên tiếp trên hành trình đó. Giá trị của hành trình là chênh lệch lớn nhất trong các chênh lệch này.

Yêu cầu

Tìm giá trị nhỏ nhất có thể của chênh lệch độ cao lớn nhất giữa hai thành phố liên tiếp trên một hành trình từ thành phố ~1~ đến thành phố ~N~.

Dữ liệu

Dữ liệu vào từ ~stdin~ gồm:

• Dòng đầu chứa hai số nguyên ~N~ và ~M~.
• Dòng thứ hai chứa ~N~ số nguyên ~H_1, H_2, \dots, H_N~.
• ~M~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~ và ~v~, cho biết có một con đường hai chiều nối hai thành phố ~u~ và ~v~.

Các số trong dữ liệu vào được ghi cách nhau bởi ít nhất một dấu cách.

Kết quả

Ghi ra ~stdout~ một số nguyên duy nhất là giá trị nhỏ nhất cần tìm.

Ví dụ

Ví dụ 1

Input

4 5
1 4 2 10
1 2
1 4
2 3
4 2
3 4

Output

6

Giải thích

Ví dụ 1

Một hành trình tối ưu là ~1 \rightarrow 2 \rightarrow 4~.

Các chênh lệch độ cao tương ứng là:

• Từ ~1~ đến ~2~: ~|1 - 4| = 3~
• Từ ~2~ đến ~4~: ~|4 - 10| = 6~

Giá trị lớn nhất trên hành trình này là ~6~, nên kết quả là ~6~.

Ràng buộc và chấm điểm

Ràng buộc

• ~N - 1 \le M \le 2 \times 10^5~
• ~0 < H_i < 10^9~

Chấm điểm

• Subtask ~1~ ~(30\%):~ ~1 \le N \le 10~
• Subtask ~2~ ~(30\%):~ ~10 < N \le 100~, ~H_i < 100~
• Subtask ~3~ ~(40\%):~ ~100 < N \le 10^5~