Bạn có biết công ty Just Odd Inventions không? Công việc của công ty này là tạo ra “những phát minh kỳ quặc” (just odd inventions). Trong bài này, ta gọi tắt là công ty JOI.

Trong một phòng thí nghiệm của công ty JOI có một mạch điện phức tạp. Mạch điện gồm \(N\) nút và \(M\) điện trở dài, mảnh. Các nút được đánh số từ \(1\) đến \(N\). Mỗi nút có thể được đặt ở một trong hai trạng thái: “điện áp cao” hoặc “điện áp thấp”. Mỗi điện trở nối hai nút và có dòng điện chạy qua khi một trong hai nút ở trạng thái “điện áp cao”, còn nút kia ở trạng thái “điện áp thấp”. Không có dòng điện chạy qua điện trở nối hai nút cùng ở trạng thái “điện áp cao” hoặc cùng ở trạng thái “điện áp thấp”.

Một ngày nọ, để bảo trì mạch điện này, công ty JOI quyết định chọn một điện trở và đặt điện áp cho từng nút sao cho chỉ điện trở được chọn không có dòng điện chạy qua, còn \(M - 1\) điện trở còn lại đều có dòng điện chạy qua. Có bao nhiêu điện trở có thể được chọn làm điện trở không có dòng điện chạy qua để thỏa mãn điều kiện này?

Công ty JOI đang dùng mạch điện kỳ quặc này để tạo ra phát minh gì là bí mật tuyệt đối ngay cả trong nội bộ công ty; ngoài giám đốc ra, không ai biết được.

Yêu cầu

Cho thông tin về mạch điện. Hãy viết chương trình tìm số điện trở có thể được chọn làm điện trở không có dòng điện chạy qua khi bảo trì.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa hai số nguyên \(N\), \(M\), cách nhau bởi một dấu cách, cho biết mạch điện có \(N\) nút và \(M\) điện trở.
• Dòng thứ \(i\) trong \(M\) dòng tiếp theo (\(1 \le i \le M\)) chứa hai số nguyên \(A_i\), \(B_i\), cách nhau bởi một dấu cách, với \(1 \le A_i \le N\), \(1 \le B_i \le N\) và \(A_i \ne B_i\). Điện trở thứ \(i\) nối nút \(A_i\) với nút \(B_i\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa số điện trở có thể được chọn làm điện trở không có dòng điện chạy qua khi bảo trì.

Ràng buộc

Tất cả dữ liệu vào đều thỏa mãn:

• \(2 \le N \le 100\,000\).
• \(1 \le M \le 200\,000\).

Phân nhóm

• Subtask 1 (10 điểm): \(N \le 1\,000\) và \(M \le 2\,000\).
• Subtask 2 (10 điểm): Từ bất kỳ nút nào cũng có thể đến bất kỳ nút nào khác bằng cách đi qua một số điện trở nối các nút; đồng thời, \(M = N\).
• Subtask 3 (35 điểm): Từ bất kỳ nút nào cũng có thể đến bất kỳ nút nào khác bằng cách đi qua một số điện trở nối các nút; đồng thời, \(M \le N + 100\).
• Subtask 4 (45 điểm): Không có ràng buộc bổ sung.

Ví dụ

4 5
1 2
1 3
1 4
2 4
3 4

1

4 4
1 2
2 3
3 2
4 3

2

13 16
1 6
2 6
3 1
3 2
4 7
4 7
5 9
6 5
8 2
8 13
9 11
10 3
11 10
11 12
12 8
13 6

3