Hệ thống mạng trên hành tinh XYZ gồm \(n\) nút mạng và \(m\) dây cáp, mỗi dây cáp nối hai nút mạng và cho phép truyền tin theo cả hai chiều. Không có hai dây cáp nào nối cùng một cặp nút, và không có dây cáp nào nối một nút với chính nó. Hệ thống đảm bảo việc truyền tin giữa hai nút bất kỳ (trực tiếp hoặc qua một số nút trung gian), đây gọi là tính liên thông của mạng. Tuy nhiên nếu một dây cáp bị hỏng, mạng có thể không còn tính liên thông nữa. Để khắc phục điều này, ban quản lý sẽ thêm vào một số dây cáp, sao cho sau khi thêm thì việc một dây cáp bất kỳ bị hỏng cũng không làm mất tính liên thông của mạng, đồng thời số dây cáp cần thêm vào là nhỏ nhất có thể. Hãy giúp ban quản lý tính số dây cáp ít nhất cần thêm để mạng đảm bảo được tính liên thông ngay cả khi có một dây cáp bất kỳ bị hỏng.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n, m\).
• \(m\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên dương \(u_i, v_i\) cho biết có một dây cáp nối giữa \(u_i\) và \(v_i\).

Output

• Ghi một số nguyên duy nhất là số dây cáp cần thêm.

Example

6 7
1 2
2 3
3 1
4 5
5 6
6 4
1 4

1

3 3
1 2
2 3
3 1

0

Scoring

• Có \(32\%\) số test với \(m = n-1\).
• Có \(32\%\) số test với \(n, m \le 1000\).
• Có \(36\%\) số test với \(n, m \le 10^5\).

Nguồn: Bài 1 ngày 2 đề chọn ĐT HSG QG TP.ĐN 2022-2023