Mỗi cặp hoa có thể được nối hoặc không nối. Hai hoa không nối \(a,b\) tự mọc thêm rễ nối nhau nếu tồn tại ít nhất hai hoa khác nhau \(c,d\) mà cả \(a\) và \(b\) đều nối với \(c,d\). Mọi rễ có thể mọc theo quy tắc này đã mọc xong.

Hãy cắt nhiều rễ hiện có nhất sao cho sau khi rễ mọc lại theo quy tắc trên, đồ thị thu được đúng như ban đầu.

Dữ liệu vào

Dòng đầu chứa \(n,m\). \(m\) dòng tiếp theo chứa \(a,b\), biểu thị hai hoa có rễ nối nhau. Các hoa được đánh số từ \(1\) đến \(n\). Đồ thị đầu vào được bảo đảm đã bão hòa theo quy tắc mọc rễ.

Dữ liệu ra

In số rễ lớn nhất có thể cắt.

Ràng buộc

• \(1\le n\le1000\), \(1\le m\le10^5\).

Phân nhóm

1. \(20\) điểm: \(n\le10\), \(m\le20\).
2. \(14\) điểm: \(m=n(n-1)/2\).
3. \(15\) điểm: mỗi hoa nối với nhiều nhất \(7\) hoa khác.
4. \(15\) điểm: \(n\le50\), \(m\le1000\).
5. \(36\) điểm: không có ràng buộc thêm.

Ví dụ

9 14
1 2
1 4
1 5
2 4
2 5
3 4
4 5
3 6
4 6
6 7
6 9
7 9
8 9
5 8

2

Nguồn

CEOI 2026 - Ngày 2, bài Flower Cutting.

Đề bài, dữ liệu kiểm thử và lời giải tham khảo được lấy từ nguồn CEOI 2026 chính thức.