• Tên file bài làm: NETWORK.cpp
• File dữ liệu vào: NETWORK.INP
• File kết quả: NETWORK.OUT
• Thời gian chạy: 1.0 giây

Đề bài

Hệ thống máy tính gồm ~n~ máy, máy thứ ~i~ có ~c_i~ cổng kết nối (~2 \le c_i \le n~). Các máy chia thành ~k~ trạm. Có ~m~ yêu cầu liên lạc ~(u, v)~ giữa các trạm.

Hàm mục tiêu cần tối thiểu hóa: ~f = E \times n + L~ Trong đó ~E~ là tổng số kết nối, ~L~ là độ trễ lớn nhất giữa hai máy bất kỳ cần liên lạc. Số kết nối của mỗi máy không được vượt quá số cổng ~c_i~.

Dữ liệu vào

• Dòng đầu ghi ~n, k, m~ (~1 \le k \le n \le 10^5, 1 \le m \le \min(k^2, 10^5)~).
• Dòng thứ hai chứa ~n~ số nguyên ~c_1, c_2, \dots, c_n~.
• Tiếp theo là ~k~ nhóm dòng mô tả ~k~ trạm.
• ~m~ dòng tiếp theo, mỗi dòng chứa hai số ~u, v~ thể hiện yêu cầu giữa trạm ~u~ và trạm ~v~.

Kết quả

• Dòng đầu in số nguyên ~f~ nhỏ nhất.
• ~E~ dòng tiếp theo in các cặp kết nối ~u \ v~ (~u < v~).

Subtask

• Subtask 1 (30% số điểm): ~n \le 6~.
• Subtask 2 (30% số điểm): ~c_i = n~ với mọi ~1 \le i \le n~.
• Subtask 3 (40% số điểm): Không có ràng buộc gì thêm.