Số tuyến cáp tối thiểu

Bối cảnh và bài toán

Một cụm máy chủ gồm nhiều vùng mạng chưa nối hoàn toàn với nhau. Kỹ sư có thể kéo thêm cáp giữa bất kỳ hai máy chủ thuộc hai vùng khác nhau.

Yêu cầu

Tính số tuyến cáp mới ít nhất cần bổ sung để toàn bộ mạng trở thành liên thông.

Input

Dòng đầu n, m; tiếp theo m cặp u, v là các kết nối hai chiều hiện có.

Output

In ra số cáp tối thiểu phải thêm.

Ràng buộc

• 1 <= n <= 2*10^5
• 0 <= m <= 2*10^5 ## Chấm điểm | Subtask | Điểm | Điều kiện | Official tests | |---|---:|---|---| | S1 | 40 | n <= 200, m <= 500 (nếu có m) | 01–08 | | S2 | 60 | Không có ràng buộc bổ sung | 09–20 |

Ví dụ 1

Input

4 2
1 2
3 4

Output

1

Giải thích. Nếu có k thành phần liên thông, cần đúng k-1 liên kết mới để ghép chúng thành một mạng duy nhất.

Ví dụ 2

Input

5 4
1 2
2 3
3 4
4 5

Output

0

Giải thích. Nếu có k thành phần liên thông, cần đúng k-1 liên kết mới để ghép chúng thành một mạng duy nhất.

Thông tin bài tập

Nguồn: Phỏng theo / Adapted from CSES Building Roads. Bản FULLHOUSE DEV đã biên tập lại bối cảnh/format theo phạm vi khóa học.