Bạc Liêu nổi tiếng với nhiều địa điểm du lịch thu hút khách du lịch khắp nơi trên cả nước đến tham quan như: Cánh đồng điện gió, Khu du lịch Giồng Nhãn, Quan âm Phật đài, Khu di tích nhạc sĩ Cao Văn Lầu,... Để đáp ứng nhu cầu du lịch ngày càng cao của du khách, dọc theo bờ biển Bạc Liêu mọc lên nhiều địa điểm vui chơi, tham quan, nghỉ dưỡng.

Khu du lịch Biển nhân tạo Bạc Liêu được thiết kế gồm $N$ hòn đảo nhân tạo được đánh số thứ tự từ $1$ đến $N$, một số hòn đảo đã có sẵn cầu nối với nhau để có thể đi qua lại giữa hai đảo. Hai đảo bất kì có không quá một cây cầu nối với nhau. Từ đảo nào du khách có thể đi sang đảo kia bằng cầu nối trực tiếp hoặc đi gián tiếp qua các đảo khác.

Để thuận tiện cho các phương tiện đi lại và giúp cho du khách có thể tham quan toàn bộ khu du lịch, Ban Quản lý khu du lịch dự kiến sẽ xây dựng thêm một số cây cầu, để từ bất kì một đảo nào đó du khách có thể đi đến tất cả các đảo còn lại trong khu du lịch. Nhằm tiết kiệm chi phí, Ban Quản lý muốn số lượng cầu xây thêm là ít nhất.

Yêu cầu: Hãy lập trình cho biết, Ban Quản lý cần xây thêm ít nhất bao nhiêu cây cầu để du khách có thể từ bất kì một đảo nào đó đi đến tất cả các đảo còn lại trong khu du lịch

12 7
6 10
2 1
5 2
2 6
3 4
9 12
11 9

4