Thành phố Đà Nẵng vừa mới mở một khu du lịch ăn uống Danang Éating Park (DÉP). Tên thì giống công viên phần mềm, mà nhìn trông cũng na ná Chợ đêm Sơn Trà.

Theo quy hoạch, khu du lịch sẽ mở ra \(n\) kiosk ăn uống, khu thứ \(i\) có khả năng hút khách tự thân là \(w_i\). Các kiosk sẽ được nối với nhau bằng \(m\) con đường hai chiều, mỗi con đường kết nối hai kiosk khác nhau. Để đảm bảo trật tự, Ban quản lý DÉP đã thiết kế, xây dựng sao cho: không có hai con đường nào cùng nối hai thành phố lại với nhau, và từ một thành phố luôn có thể đi tới các thành phố khác thông qua \(m\) con đường đã xây. Nói cách khác, đây chính là đồ thị đơn vô hướng liên thông, có trọng số ở đỉnh.

GSPVH sau khi chơi đủ 3 triệu để nâng hạng thẻ Helio từ Hồng lên Vàng, thì rất được Helio quan tâm. Biết rằng Giáo sư rất thích trà sữa, Helio hỏi ông có muốn mở một cửa hàng trà sữa trong khuôn viên của DÉP hay không, nếu có thì họ sẽ hỗ trợ Giáo sư cả về chi phí lẫn thủ tục (đúng là thẻ vàng có khác)

Đúng lúc này, sau khi xem xét luồng giao thông đường (đi) bộ dự kiến, Ban quản lý quyết định sẽ định chiều toàn bộ \(m\) con đường này lại, biến chúng thành đường một chiều hết, đồng thời xây dựng vài cọn đường nhỏ để nếu có ai bí đường không thể quay lại thì có thể men theo chúng, nhưng chúng ta không cần quan tâm tới những con đường này.

Vì sự thay đổi này, nên sau khi định chiều đồ thị, khả năng hút khách thực sự \(p_u\) của khu thứ \(u\) sẽ bằng tổng khả năng hút khách tự thân \(w_v\) của các đỉnh \(v\) có thể đi được từ \(u\).

Để đảm bảo sự công bằng cũng như thu hút nhiều khách du lịch nhất có thể, Ban quản lý Danang Éating Park mong muốn định chiều \(m\) cạnh sao cho \(p_u\) nhỏ nhất trong số \(n\) khu bán hàng là lớn nhất có thể. Biết rằng GSPVH có nhiều đàn em như bạn, ban quản lý nhờ Giáo sư hỏi bạn xử lý bài toán này. Hãy giúp họ nhé!

Input

• Dòng đầu tiên chứa hai số \(n, m\) \((1 \leq n, m \leq 4 \times 10^{5})\) - là số kiosk và số đường đi trong khu ăn uống DÉP.
• Dòng thứ hai chứa \(n\) số nguyên \(w_1, w_2, \ldots, w_n\) \((1 \leq w_i \leq 10^{9})\) - \(w_i\) là khả năng hút khách tự thân của đỉnh \(i\)
• \(m\) dòng tiếp theo, mỗi dòng chứa hai số \(u\), \(v\) \((1 \leq u, v \leq n)\) thể hiện một đường đi giữa hai kiosk \(u\) và \(v\).

Output

• Dòng đầu tiên in ra một số nguyên thể hiện khả năng hút khách nhỏ nhất trong phương án tối ưu.
• \(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\) thể hiện con đường được định chiều từ \(u\) đến \(v\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n, m \le 20\).
• Subtask \(2\) (\(20\%\) số điểm): \(n, m \le 2000\).
• Subtask \(3\) (\(20\%\) số điểm): \(m < n\).
• Subtask \(4\) (\(20\%\) số điểm): \(w[i] = w[i + 1] \forall 1 \leq i \leq n - 1\).
• Subtask \(5\) (\(20\%\) số điểm): Không có giới hạn gì thêm.

Sample

Test 1

Input

7 8
1 2 2 3 1 3 4
2 4
2 5
6 3
1 3
1 7
4 5
1 6
5 1

Output

6
2 4
5 2
3 6
1 3
7 1
4 5
6 1
5 1
****
*********

Note

Đây là biểu diễn đồ thị của đáp án được đưa ra:

Khi đó, \(p = {6, 12, 6, 12, 12, 6, 10}\), vì vậy \(\min p_i = p[1] = 6\).
Có thể chứng minh được không có cách định chiều đồ thị nào có \(\min p_i < 6\).