사진

농부 존은 한 줄로 서 있는 $N$마리의 소 ($2 \le N \le 10^9$)를 사진으로 찍으려고 합니다. 소들은 왼쪽부터 오른쪽 순서로 $1$번부터 $N$번까지 번호가 매겨져 있습니다. 사진 한 장은 줄에서 연속한 구간에 있는 소들을 담을 수 있으며, 존은 모든 소가 적어도 한 장의 사진에는 나오도록 만들고 싶습니다.

그런데 서로 사이가 나쁜 소들의 쌍이 $K$개 ($1 \le K \le 1000$) 있습니다. 각 쌍은 같은 사진에 함께 찍히는 것을 거부합니다. 사이가 나쁜 쌍들의 위치가 주어질 때, 존이 찍어야 하는 사진의 최소 개수를 구하세요.

• 첫째 줄: 공백으로 구분된 두 정수 $N$과 $K$가 주어집니다.
• 둘째 줄부터 $K+1$째 줄까지: $i+1$째 줄에는 두 정수 $A_i$와 $B_i$가 주어집니다. 이는 위치 $A_i$와 위치 $B_i$에 있는 두 소가 사이가 나빠 같은 사진에 함께 찍힐 수 없음을 의미합니다 ($1 \le A_i, B_i \le N$, $A_i \ne B_i$).

• 첫째 줄: 존이 찍어야 하는 사진의 최소 개수를 나타내는 정수 하나를 출력합니다.

$N = 7$이고 사이가 나쁜 쌍이 $(1, 3)$, $(2, 4)$, $(5, 6)$인 경우, 존은 다음과 같이 사진 3장을 찍을 수 있습니다.

• $1$번부터 $2$번까지 한 장
• $3$번부터 $5$번까지 한 장
• $6$번부터 $7$번까지 한 장