Hành trình cứu trợ

Năm 2025, Việt Nam là quốc gia liên tiếp chịu sức tàn phá nặng nề của các cơn bão, hoàn lưu của các cơn bão gây mưa lớn và ngập lụt nhiều nơi. Những ngày gần đây các tỉnh miền Trung bị ngập lụt nặng, nhiều khu dân cư bị cô lập. Với tinh thần ``lá lành đùm lá rách'' của dân tộc, nhiều tổ chức, cá nhân đã quyên góp ủng hộ đồng bào miền Trung khắc phục thiên tai.

Dữ liệu về khu vực cần cứu trợ được chia thành \(n\) trạm dừng và \(m\) đường đi hai chiều nối các trạm dừng đó. Các trạm dừng được đánh số lần lượt từ \(1\) đến \(n\), trạm dừng thứ \(i\) có mực nước là \(d_i\), các đường đi được đánh số hiệu lần lượt từ \(1\) đến \(m\). Người ta muốn chuyển hàng cứu trợ từ trạm dừng \(1\) tới trạm dừng \(n\). Quá trình di chuyển đi qua một số trạm dừng, tuy nhiên nếu chênh lệch về mực nước giữa hai trạm dừng liên tiếp trên hành trình là quá cao thì có thể ảnh hưởng đến an toàn của đoàn cứu trợ.

Yêu cầu: Hãy chỉ ra một hành trình mà độ lệch mực nước lớn nhất giữa hai trạm dừng liên tiếp bất kỳ trên hành trình là nhỏ nhất.

Input

Dữ liệu vào:

• Dòng \(1\): Chứa hai số nguyên dương \(n, m\) (\(2 \le n \le 10^5\), \(m \le 2 \cdot 10^5\)).

• Dòng \(2\): Chứa \(n\) số nguyên dương \(d_1, d_2, \ldots, d_n\) (\(d_i \le 10^9\), \(1 \le i \le n\)) lần lượt là mực nước của các trạm dừng.

• \(m\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên dương \(u, v\) cho biết giữa hai trạm dừng \(u\) và \(v\) có đường đi mang số hiệu \(i\).
  Dữ liệu đảm bảo luôn tồn tại hành trình từ trạm dừng \(1\) tới trạm dừng \(n\).

Các số trên một dòng của dữ liệu vào ghi cách nhau ít nhất một dấu cách.

Ràng buộc:

• Có \(30\%\) số test ứng với \(30\%\) số điểm thỏa mãn: \(2 \le n \le 10^3\), \(1 \le m \le 10^3\) và mực nước của các trạm dừng bằng nhau;

• \(30\%\) số test khác ứng với \(30\%\) số điểm thỏa mãn: \(2 \le n \le 10^3\), \(1 \le m \le 10^3\);

• \(40\%\) số test còn lại ứng với \(40\%\) số điểm không có ràng buộc gì thêm.

Output

In ra:

• Dòng \(1\): Ghi độ lệch mực nước lớn nhất giữa hai trạm dừng liên tiếp bất kỳ trên hành trình tìm được.

• Dòng \(2\): Ghi số hiệu các đường đi theo đúng thứ tự trên hành trình. Nếu có nhiều hành trình thỏa mãn thì ghi một hành trình bất kỳ.
  Các số trên một dòng của dữ liệu ra ghi cách nhau ít nhất một dấu cách.

Example

Input:

5 6
10 12 18 20 25
1 3
1 2
1 4
2 3
3 4
4 5

Output:

6
2 4 5 6

Note

Hành trình qua các trạm dừng: \(1 \to 2 \to 3 \to 4 \to 5\). Số hiệu các tuyến đường đi: \(2 \to 4 \to 5 \to 6\).

Độ lệch mực nước lớn nhất giữa hai trạm dừng liên tiếp là giữa trạm dừng \(2\) và \(3\): \(|12 - 18| = 6\).