Problem
Một tiểu bang nằm rải rác trên các hòn đảo của Châu Đại Dương đã quyết định tạo ra một mạng lưới đường bộ (hay đúng hơn là những cây cầu). Mỗi cây cầu có thể được điều hướng theo cả hai hướng. Một kế hoạch trình tự cho việc xây dựng các cây cầu đã được phát triển và được biết rằng sau khi xây dựng tất cả các cây cầu, có thể lái xe qua chúng từ đảo này sang đảo khác (có thể qua một số đảo trung gian
Tuy nhiên, thời điểm này có thể đến trước khi tất cả các cây cầu được xây dựng. Bạn cần xác định số lượng cầu tối thiểu như vậy, sau khi xây dựng (theo thứ tự được xác định bởi kế hoạch), có thể đi từ bất kỳ hòn đảo nào sang bất kỳ hòn đảo nào khác.
Đầu vào
Dòng đầu tiên chứa hai số: số đảo N (1≤N≤10000) và số cây cầu trong kế hoạch M (1≤M≤50000). Sau đó, có M dòng, mỗi dòng chứa hai số x và y (1≤x,y≤N) - số của các thành phố được kết nối bởi cây cầu tiếp theo trong kế hoạch.
Đầu ra
Chương trình sẽ xuất ra một số duy nhất - số lượng cầu tối thiểu được xây dựng, sau đó có thể đi từ bất kỳ hòn đảo nào sang bất kỳ hòn đảo nào khác.
| Đầu vào |
Đầu ra |
|
4 5
1 2
1 3
2 3
3 4
4 1
|
4 |