THỰC HÀNH

Tổng công ty MeKa có N máy tính được đánh số từ 1 đến N. Người ta lắp đặt được M 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 u và 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 u=m₀, m₁, ....,m_k=v sao cho giữa hai máy tính m_i-1 và m_i bất kỳ (i=1,...,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ị 58 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.

Input:

• Dòng đầu tiên chứa hai số nguyên dương N, M (0<N≤5000; M≤200000)
• M dòng tiếp theo chứa thông tin về M kênh truyền tin đã được lắp đặt. Mỗi dòng chứa 2 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.

Output:

• Dòng đầu tiên ghi K là số lượng kênh truyền tin cần lắp đặt thêm
• K dòng tiếp theo mô tả thông tin về K 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.

Các số trên một dòng cách nhau ít nhất một dấu cách.

Example:

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

Output:
2
1 5
1 7