Buổi liên khối chuyên Tin của trường Nguyễn Bỉnh Khiêm diễn ra với sự tham gia của \(N\) học sinh. Cuối giờ, Oanh Trúc Béo ra hiệu cho các học sinh này xếp thành một hàng và đánh số họ từ \(1\) đến \(N\) tương ứng với vị trí đứng của họ trong hàng. Oanh Trúc muốn chụp một số tấm ảnh kỷ niệm cho buổi liên khối, mỗi tấm sẽ chụp lại một đoạn liên tiếp các bạn trong hàng. Vì là một sự kiện trong đại nên Trúc muốn mỗi bạn học sinh tham dự đều có mặt trong ít nhất một tấm ảnh.

Tuy nhiên, trong \(N\) học sinh này có tồn tại \(K\) đôi bạn xung khắc nhau (đã từng là bạn thân nhưng hiện tại tình nghĩa đã vô cùng rạn nứt vì crush chung một em gái nào đó), các đôi bạn xung khắc này đều không muốn đứng chung với nhau trong một tấm ảnh. Bộ nhớ của điện thoại Oanh Trúc không còn nhiều nên cô ấy đã nhờ bạn lập trình tính toán số tấm ảnh ít nhất cần chụp để thỏa mãn tất cả các ràng buộc trên.

Input

• Dòng đầu chứa hai số nguyên dương \(N\) và \(K\) (\(2\leq N\leq 10^9\), \(2\leq K\leq 1000\)).

• Dòng thứ \(i\) trong \(K\) dòng tiếp theo chứa hai số nguyên dương phân biệt \(A_i\) và \(B_i\) thể hiện một đôi bạn xung khắc \(\left(A_i, B_i\right)\) - họ không thể cùng đứng chung trong một tấm ảnh.

Output

• Một số nguyên duy nhất là số tấm ảnh ít nhất mà Oanh Trúc Béo cần chụp.

Example

7 3
1 3
2 4
5 6

3