Trong buổi tập trung học sinh đầu năm học, có Bình muốn chụp ảnh ~N~ học sinh của mình đang đứng thành một hàng được đánh số từ ~1~ đến ~N~ theo thứ tự từ trái qua phải. Một bức ảnh có thể chụp được một đoạn liên tiếp các học sinh trong một hàng. Mỗi học sinh phải có mặt trong ít nhất một bức ảnh.

Tuy vậy, trong hàng lại có ~K~ cặp học sinh ghét nhau tới nỗi hai học sinh trong cùng một cặp không muốn xuất hiện trong cùng một bức ảnh. Cho biết các cặp học sinh ghét nhau, hãy tính xem cô Bình cần chụp ít nhất bao nhiêu bức ảnh.

INPUT

Dòng đầu tiên gồm hai số nguyên ~N~ và ~K~ (~2 \leq N \leq 10^9~, ~1 \leq K \leq 1000~).

~K~ dòng tiếp theo, dòng thứ ~i~ chứa hai số ~a_i~ và ~b_i~ cho biết một cặp học sinh ghét nhau và không muốn xuất hiện chung trong một bức ảnh.

OUTPUT

Một số nguyên là số bức ảnh mà cô Bình cần phải chụp.

SAMPLE INPUT

8 3
1 4
2 3
5 6

SAMPLE OUTPUT

3

Giải thích: Cô Bình cần phải chụp 3 bức ảnh:

• Tấm thứ nhất gồm học sinh ~1, 2~.
• Tấm thứ hai gồm học sinh ~3, 4, 5~.
• Tấm thứ ba gồm học sinh ~6, 7, 8~.