Kết nối thành phố

NewYearLand có \(N\) thành phố và \(M\) con đường hiện tại. Mục tiêu là xây dựng số lượng con đường mới tối thiểu để đảm bảo rằng có một tuyến đường giữa hai thành phố bất kỳ, tức là làm cho đồ thị trở nên liên thông.

Nhiệm vụ của bạn là:

• Tìm ra số lượng đường tối thiểu cần thiếu.
• Chỉ ra những con đường mới nào nên được xây dựng để nối tất cả các thành phần liên thông thành một khối duy nhất.

Input

• Dòng đầu tiên có hai số nguyên \(N\) và \(M\): số lượng thành phố và số con đường hiện tại (\(1 \le N \leq 10^5, 1 \leq M \leq 2 \cdot 10^5\)).
• \(M\) dòng tiếp theo mô tả các con đường. Mỗi dòng có hai số nguyên \(a\) và \(b\): có một đường giữa thành phố \(a\) và \(b\).

Output

• Dòng đầu tiên in một số nguyên \(K\): số lượng con đường tối thiểu cần thiết.
• \(K\) dòng tiếp theo mô tả các con đường mới cần xây dựng. Mỗi dòng chứa hai số nguyên \(u\) và \(v\) là hai thành phố được nối.

Example

6 3
1 2
1 3
4 6

2
1 4
1 5