Vương quốc Byteland có ~N~ thành phố được đánh số từ ~1~ đến ~N~. Độ cao của thành phố thứ ~i~ là ~H_i~. Hệ thống giao thông của vương quốc gồm ~M~ con đường hai chiều đảm bảo giữa hai thành phố bất kì đều có thể đến được với nhau, mỗi con đường nối hai thành phố phân biệt. Hành trình của đoàn công tác đã chọn xuất phát từ thành phố ~1~ đi đến thành phố ~N~ sao cho chênh lệch độ cao lớn nhất giữa hai thành phố liên tiếp nhau trên đường đi là nhỏ nhất.

Yêu cầu: Tìm giá trị chênh lệch độ cao lớn nhất giữa hai thành phố liên tiếp nhau của hành trình mà đoàn công tác đã chọn.

Dữ liệu vào

• Dòng đầu ghi hai số nguyên ~N~, ~M~ (~N - 1 \le M \le 2 \times 10^5~);
• Dòng thứ hai ghi ~N~ số nguyên lần lượt ~H_1, H_2, \ldots, H_N~ (~0 \le H_i \le 10^6~);
• Trong ~M~ dòng tiếp theo, mỗi dòng ghi hai số nguyên ~u~ và ~v~ cho biết có một con đường nối giữa hai thành phố.

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

Kết quả

• Một số duy nhất là giá trị chênh lệch tìm được.

Ví dụ

Đầu vào:

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

Đầu ra:

6

Giải thích: Hành trình đoàn công tác là ~1 \rightarrow 2 \rightarrow 4~, chênh lệch độ cao lần lượt là: từ ~1 \rightarrow 2~: ~|1 - 4| = 3~; từ ~2 \rightarrow 4~: ~|4 - 10| = 6~. Do đó kết quả là ~\max(3, 6) = 6~.

Giới hạn

• ~N - 1 \le M \le 2 \times 10^5~, ~0 \le H_i \le 10^6~

Điểm của một subtask chỉ được tính khi tất cả các test thuộc subtask đó đều đúng.