Xây dựng đường

Trong một buổi họp quy hoạch thành phố, FullHouse Dev được giao nhiệm vụ kết nối các khu dân cư trong thành phố Byteland. Hiện tại, thành phố có một số con đường nối các khu dân cư, nhưng chưa đảm bảo việc di chuyển thuận tiện giữa tất cả các khu. Với tinh thần trách nhiệm, FullHouse Dev bắt tay vào việc tính toán số lượng con đường tối thiểu cần xây dựng thêm.

Bài toán

Byteland có \(n\) khu dân cư và \(m\) con đường nối giữa chúng. Nhiệm vụ của FullHouse Dev là xây dựng thêm các con đường mới sao cho có thể di chuyển giữa bất kỳ hai khu dân cư nào trong thành phố.

INPUT FORMAT:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\): số lượng khu dân cư và số con đường hiện có. Các khu dân cư được đánh số từ \(1\) đến \(n\).
• \(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a\) và \(b\): thể hiện có một con đường nối giữa khu dân cư \(a\) và khu dân cư \(b\).
• Mỗi con đường luôn nối hai khu dân cư khác nhau và giữa hai khu dân cư bất kỳ chỉ có tối đa một con đường.

OUTPUT FORMAT:

• Dòng đầu tiên in ra số nguyên \(k\): số lượng con đường cần xây dựng thêm.
• \(k\) dòng tiếp theo, mỗi dòng mô tả một con đường mới cần xây. Bạn có thể in ra bất kỳ phương án hợp lệ nào.

Ràng buộc:

• \(1 \leq n \leq 10^5\)
• \(1 \leq m \leq 2 \cdot 10^5\)
• \(1 \leq a,b \leq n\)

Ví dụ

INPUT

4 2
1 2
3 4

OUTPUT

1
2 3

Giải thích

Ban đầu thành phố có 4 khu dân cư và 2 con đường: một con đường nối khu 1 và 2, một con đường nối khu 3 và 4. Để đảm bảo có thể di chuyển giữa mọi khu dân cư, FullHouse Dev chỉ cần xây thêm 1 con đường nối khu 2 và 3. Như vậy sẽ tạo thành một đường đi liên thông giữa tất cả các khu dân cư.