Mô tả bài toán: Xây đường

Byteland có n thành phố và m con đường nối giữa các thành phố. Nhiệm vụ là xây dựng thêm các con đường mới sao cho có thể có một đường đi giữa mọi cặp thành phố.

Bạn cần tìm ra:

1. Số lượng đường tối thiểu cần xây.
2. Danh sách các đường mới cần xây.

Input:

• Dòng đầu tiên chứa hai số nguyên n và m: số lượng thành phố và số lượng đường hiện tại.
• Sau đó, có m dòng, mỗi dòng chứa hai số nguyên a và b: có đường nối giữa thành phố a và b.

Output:

• Dòng đầu tiên in một số nguyên k: số lượng đường mới cần xây dựng.
• Sau đó, in ra k dòng, mỗi dòng gồm hai số nguyên đại diện cho các đường mới.

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:

• Đồ thị có 2 thành phần liên thông: {1, 2} và {3, 4}.
• Cần 1 đường để nối các thành phần, ví dụ nối đỉnh 2 với đỉnh 3.