C. BLUEHOUSE - Ngôi nhà xanh

Bộ nhớ: 256 MiB Thời gian: 500 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: Trình chấm ngoài

Đề bài

Trên một vùng đất xa xôi có một ngôi nhà xanh với rất nhiều phòng cũng được quét vôi màu xanh. Các phòng màu xanh này được nối với nhau bằng các hành lang màu vàng. Các hành lang này đảm bảo giữa hai phòng bất kỳ luôn có thể đi được đến nhau.

Người chủ nhà nhận thấy rằng có một số hành lang quan trọng hơn bình thường vì khi bỏ nó đi thì có một số phòng không thể đi đến được nhau.

Vào một ngày đẹp trời, chủ nhà muốn bạn đưa ra một danh sách ít nhất các hành lang cần xây dựng thêm để không còn tồn tại hành lang nào quan trọng hơn bình thường như thế nữa.

Dữ liệu vào:

  • Dòng đầu ghi hai số nguyên dương N, M là số phòng và số hành lang. Các phòng được đánh số từ 1 đến N\ (1≤N≤50000; 1≤M≤100000) ;
  • M dòng tiếp theo, mỗi dòng ghi hai số x, y thể hiện có một hành lang nối phòng x với phòng y .

Dữ liệu ra:

  • Dòng đầu ghi K là số lượng hành lang ít nhất cần xây dựng thêm;
  • Mỗi dòng trong K dòng tiếp theo ghi hai số thể hiện một hành lang cần xây dựng thêm.

Ví dụ:

Dữ liệu vào:
5 5
1 2
1 3
2 3
2 4
3 5
Dữ liệu ra:
1
4 5