Trên mảnh đất của những con số, có ~N + 1~ số tự nhiên từ ~0~ đến ~N~ đang sinh sống với nhau. Tuy nhiên, có ~M~ cặp số ~(x_i, y_i)~ đang ghét nhau ~(i = 1..M)~.

Để tránh mâu thuẫn dẫn đến chiến tranh, nhà vua (số ~0~) muốn chia đất nước thành các vùng sao cho:

• Mỗi số thuộc đúng một vùng.

• Mỗi vùng gồm các số tự nhiên liên tiếp.

• Ở mỗi vùng, không có ~2~ số nào ghét nhau.

Số vùng ít nhất nhà vua có thể chia là bao nhiêu?

Input

Dòng đầu tiên chứa ~2~ số nguyên dương ~N~ và ~M~ ~(1 \le N \le 10^9, 1 \le M \le 10^5)~.

Trong ~M~ dòng tiếp theo, mỗi dòng chứa ~2~ số nguyên dương ~x~ và ~y~ thể hiện một cặp số ghét nhau ~(1 \le x, y \le N; x ≠ y)~.

Output

Số vùng ít nhất có thể.

Sample Input 1

7 3
1 3
2 4
5 6

Sample Output 1

3

Notes

Chia các số như sau: ~(1~ ~2), (3~ ~4~ ~5), (6~ ~7)~.