Anh nông dân Giang muốn kết nối N nông trại bằng mạng cáp quang để cho một số cặp nông trại có thể giao tiếp với nhau. Các nông trại nằm xung quanh một hồ lớn và Giang chỉ có thể kết nối các nông trại liền kề nhau. Nông trại i sẽ kết nối tới nông trại i − 1 và i + 1 (Nông trại N nối với nông trại 1). Do chỉ có một số cặp nông trại có nhu cầu giao tiếp với nhau nên anh ta muốn xây dựng số lượng kết nối ít nhất mà vẫn thoả vẫn tất cả các cặp có thể giao tiếp được.

Dữ liệu vào

Dòng đầu chứa 1 số nguyên dương N (N ≤ 1000).
Dòng thứ 2 chứa một số nguyên dương P (là số cặp nông trại cần liên lạc với nhau, P ≤ 10000).
Dòng thứ 3 đến dòng thứ P + 2 là hai số nguyên chỉ hai nông trại cần kết nối. Không có cặp số nào được lặp lại trong danh sách.

Kết quả

Ghi ra một số duy nhất chỉ số lượng kết nối trực tiếp tối thiểu mà Giang cần.