Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

CLCOMNET - Mạng máy tí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=m0, m1, ....,mk=v sao cho giữa hai máy tính mi-1 và mi 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

Được gửi lên bởi:noname00.pas
Ngày:2017-11-11
Thời gian chạy:0.100s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C-CLANG C CSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG C99 JAVA PAS-FPC PYTHON PYTHON3
Nguồn bài:Bài tập thực hành CSL (Lào Cai cung cấp)

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.