Problem
TậpX: FIRION ẤN ĐỘ TRỞ LẠI
Berland cuối cùng đã trở nên mạnh mẽ hơn sau thất bại nặng nề trong cuộc chiến chống lại Sterland, và Hoàng đế của Berland Firion đang chuẩn bị tấn công kẻ thù.
Sterland là một số thành phố nhất định được kết nối bằng đường hai chiều. Từ bất kỳ thành phố nào của Sterland, bạn có thể đến bất kỳ thành phố nào khác. Không có con đường nào kết nối thành phố với chính nó.
Kế hoạch như sau:
Thành phố bị tấn công được chọn. Thành phố bị phá hủy, và những con đường phát ra từ nó bị rào chắn. Đồng thời, Sterland sẽ mất đi tính toàn vẹn của nó. Tiếp theo, một trong những khu vực hình thành bị tấn công. Trong trường hợp này, diện tích này ít nhất phải là 1/8 và không quá 1/4
từ phần còn lại của đất nước (diện tích được đo bằng số lượng thành phố trong một khu vực nhất định). Nếu Sterland vẫn còn nguyên vẹn khi một thành phố bị phá hủy hoặc không có khu vực thích hợp nào được hình thành, thì thành phố này không thích hợp để tấn công.
Firion muốn biết có bao nhiêu thành phố đáp ứng các điều kiện trên và số lượng các thành phố này theo thứ tự tăng dần.
Đầu vào
Dòng đầu tiên chứa hai số: n – số thành phố ở Sterland ( 2 <= n <= 10^3), m – số đường ở Sterland ( 1 <= m <= 10^4).
Khi đó có m dòng chứa nội dung mô tả các con đường, cụ thể: mỗi dòng ghi 2 số: X và Y. Điều này có nghĩa là thành phố X và thành phố Y được nối với nhau bằng một con đường.
Dấu ấn
Trong dòng đầu tiên in số s – số thành phố thích hợp để tấn công. Ở dòng thứ hai in s số - số lượng các thành phố đó theo thứ tự tăng dần.
Ví dụ
5 5
1 2
1 3
23
34
4 5 |
1
4 |