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

Đề bài

Hệ thống gồm ~n~ máy tính phân vào ~k~ trạm. Có ~m~ yêu cầu liên lạc giữa các trạm. Đặc biệt, trong bài toán này, mọi máy tính đều có đủ cổng kết nối để nối với tất cả các máy khác, tức là ~c_i = n~ với mọi ~1 \le i \le n~.

Hàm chi phí ~f = E \times n + L~. Vì mỗi thành phần liên thông gồm ~V~ máy cần ~V - 1~ cạnh và có thể cấu hình thành mạng hình sao (Star Topology) có độ trễ ~L \le 2~.

Yêu cầu: Hãy thiết kế mạng có ~f~ nhỏ nhất và in ra các cạnh nối.

Dữ liệu vào

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

Kết quả

• Dòng đầu ghi giá trị ~f~.
• ~E~ dòng tiếp theo ghi các cạnh kết nối ~u \ v~ (~u < v~).

Subtask

• Subtask 1 (40% số điểm): ~n \le 1000, m \le 2000~.
• Subtask 2 (60% số điểm): Không có ràng buộc gì thêm.

Sample Input

4 3 2
4 4 4 4
1
1
2
2 3
1
4
1 2
2 3

Sample Output

14
1 2
1 3
1 4