Tổng công ty MeKa có máy tính được đánh số từ đến . Người ta lắp đặt được kênh trực tiếp truyền tin hai chiều giữa một số cặp máy. Hai máy tính và trong Tổng Công ty được coi là có thể truyền tin được cho nhau nếu chúng được nối với nhau bằng một kênh nối trực tiếp hoặc tồn tại một dãy các máy tính sao cho giữa hai máy tính và bất kỳ đều có ít nhất một kênh nối trực tiếp. Nhằm triển khai thực hiện chủ trương cải cách hành chính theo tinh thần Chỉ thị của Bộ Chính trị. Ban Giám đốc đã cho triển khai dự án hoàn thiện mạng máy tính để nâng cao hiệu quả hoạt động của Tổng Công ty.
Yêu cầu: Hãy giúp Ban Giám đốc xác định số lượng ít nhất kênh nối trực tiếp tuyền tin cần lắp đặt thêm, sao cho hai máy tính bất kỳ trong Tổng Công ty có thể truyền tin được cho nhau.
Dữ liệu vào:
Dòng đầu tiên chứa hai số nguyên dương ;
dòng tiếp theo chứa thông tin về kênh truyền tin đã được lắp đặt. Mỗi dòng chứa số nguyên dương xác định hai máy tính được nối trực tiếp bởi kênh truyền tin đã lắp đặt.
Dữ liệu ra:
Dòng đầu tiên ghi là số lượng kênh truyền tin cần lắp đặt thêm;
dòng tiếp theo mô tả thông tin về kênh tìm được. Mỗi dòng chứa hai số nguyên xác định hai máy tính cần lắp đặt thêm kênh nối giữa chúng. Trong trường hợp có nhiều hơn một cách nối, chỉ cần đưa ra một cách.
Trong dữ liệu vào và dữ liệu ra, các số trên một dòng cách nhau ít nhất một dấu cách.
