Quốc đảo xinh đẹp Alibaba nằm ở biển đông với ~N~ hòn đảo và được kết nối với nhau bởi các cây cầu. Hai đảo kết nối trực tiếp với nhau không quá một cây cầu. Nhằm tổ chức Festival biển đảo, Thủ tướng ra dự án nâng cấp các cây cầu. Lần lượt các cây cầu sẽ được nâng cấp, sửa chữa. Trong quá trình đó cây cầu đang sửa chữa sẽ không được lưu thông.

Nhằm đảm bảo giao thông thông suốt giữa các hòn đảo Thủ tướng cho phép bắc cầu phao (cầu dùng tạm). Bài toán đặt ra giúp Thủ tướng là trong suốt quá trình nâng cấp hết các cây cầu cần bắc số cầu phao ít nhất là bao nhiêu? Tuy nhiên một ràng buộc đưa ra là về mặt thẩm mỹ và an toàn lao động không cho phép bắt cầu phao song song với cầu đã có.

Input

Dòng thứ nhất gồm hai số nguyên ~N, M~ thỏa ~3 \le N \le 2500; 2 \le M \le 20000~.

~M~ dòng tiếp theo chứa bộ ~p_i, q_i~ là cầu nối giữa hai đảo thỏa ~p_i < q_i; 1 \le p_i, q_i \le N~.

Output

In ra số cầu phao ít nhất cần bắc.

Samples

Sample Input 1

4 3
1 2
2 3
2 4

Sample Output 1

2