Công trường khai thác than có thể được xem như một đồ thị vô hướng gồm các đường hầm kết nối các điểm khai thác. Để đảm bảo an toàn, cần thiết lập các lối thoát hiểm tại một số điểm khai thác, sao cho khi tai nạn xảy ra (bất kỳ một điểm khai thác nào bị sập), công nhân ở các điểm khai thác khác vẫn luôn có một con đường dẫn đến lối thoát hiểm.
Hãy viết một chương trình để tính toán số lượng lối thoát hiểm ít nhất cần thiết lập, cũng như tổng số phương án đặt lối thoát hiểm tối ưu khác nhau.
Dữ liệu:
File đầu vào gồm nhiều bộ dữ liệu.
Dòng đầu tiên của mỗi bộ dữ liệu là một số nguyên dương , biểu thị số lượng đường hầm của công trường.
dòng tiếp theo, mỗi dòng là hai số nguyên và cách nhau bởi dấu cách, biểu thị điểm khai thác và điểm khai thác được nối trực tiếp bởi một đường hầm.
Dữ liệu kết thúc bằng số .
Kết quả:
Số dòng trong file đầu ra tương ứng với số bộ dữ liệu trong file đầu vào. Mỗi dòng tương ứng với kết quả của một bộ dữ liệu.
Dòng thứ bắt đầu bằng Case i: (lưu ý chữ hoa chữ thường, giữa Case và i có dấu cách, giữa i và : không có dấu cách, sau : có dấu cách). Tiếp theo là hai số nguyên dương cách nhau bởi dấu cách: số đầu tiên là số lượng lối thoát hiểm ít nhất cần thiết lập cho bộ dữ liệu thứ , số thứ hai là tổng số phương án thiết lập tối ưu khác nhau.
