Chụp Ảnh Đàn Bò

Có $N$ con bò đứng thành một hàng, đánh số từ $1$ đến $N$. Cần chụp ảnh toàn bộ đàn bò, mỗi tấm ảnh chụp một đoạn liên tiếp các con bò. Mỗi con bò phải xuất hiện trong ít nhất một tấm ảnh.

Có $K$ cặp bò không thân thiện — hai con bò trong một cặp không được cùng xuất hiện trong cùng một tấm ảnh.

Tìm số tấm ảnh tối thiểu cần chụp để thỏa mãn tất cả điều kiện.

Dữ liệu vào

• Dòng đầu: hai số nguyên $N$ và $K$
• $K$ dòng tiếp theo: mỗi dòng gồm hai số nguyên $A_i$ và $B_i$ — cặp bò không thân thiện ($A_i\ne B_i$)

Dữ liệu ra

Một số nguyên — số tấm ảnh tối thiểu cần chụp.

Ràng buộc

• $2\le N\le {10}^9$
• $1\le K\le 1000$
• $1\le A_i,B_i\le N$

Ví dụ