• Tên file bài làm: SPANTREE.cpp
• File dữ liệu vào: SPANTREE.INP
• File kết quả: SPANTREE.OUT
• Thời gian chạy: 1.0 giây

Đề bài

Cho đơn đồ thị vô hướng gồm ~N~ đỉnh và ~M~ cạnh. Đồ thị có thể gồm nhiều thành phần liên thông. Với mỗi thành phần liên thông có ~V~ đỉnh, ta muốn chọn ra đúng ~V - 1~ cạnh thuộc đồ thị ban đầu sao cho ~V~ đỉnh này liên thông với nhau (tạo thành một rừng cây khung).

Yêu cầu: Hãy tìm số lượng cạnh tối thiểu cần giữ lại và in ra danh sách các cạnh đó.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên dương ~N, M~ (~1 \le N \le 10^5, 0 \le M \le 2 \times 10^5~).
• ~M~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u, v~ (~1 \le u, v \le N, u \ne v~) mô tả một cạnh của đồ thị.

Kết quả

• Dòng đầu tiên ghi số nguyên ~E~ là tổng số cạnh của rừng cây khung.
• ~E~ dòng tiếp theo, mỗi dòng in ra hai đỉnh ~u, v~ thể hiện một cạnh được chọn (~u < v~). Thứ tự in cạnh tùy ý.

Subtask

• Subtask 1 (40% số điểm): ~N \le 1000, M \le 2000~.
• Subtask 2 (60% số điểm): Không có ràng buộc gì thêm.

Ví dụ