Giải bài trực tuyến

Một công ty máy tính bán hàng cho các khách hàng ở N thành phố (3 ≤ N ≤ 35) đánh số từ 1 đến N. Có M đoạn đường, mỗi đoạn đường nối hai thành phố nào đó. Công ty muốn mở các trung tâm bảo hành đặt tại một số thành phố này sao cho mỗi thành phố hoặc là có trung tâm bảo hành đặt tại nó hoặc có trung tâm bảo hành đặt ở thành phố có đoạn đường nối trực tiếp với nó.

Yêu cầu: Hãy xác định xem công ty cần mở ít nhất bao nhiêu trung tâm để đáp ứng điều kiện trên.

Dữ liệu

• Dòng đầu tiên chứa hai số N, M cách nhau bởi dấu cách.
• Mỗi dòng trong số M dòng tiếp theo chứa hai số nguyên là các chỉ số của các đầu mút của một trong số M đoạn đường.

Kết qủa

Ghi ra số lượng trung tâm bảo hành ít nhất cần mở.

Hạn chế

• Có 40% số test có 3 ≤ N ≤ 15.

Ví dụ

Dữ liệu:
8 12
1 2
1 6
1 8
2 3
2 6
3 4
3 5
4 5
4 7
5 6
6 7
6 8

Kết qủa
2