Farmer John은 한 줄로 선 $N$마리 소($(1 \le N \le 200,000)$)의 파노라마 사진을 만들려 합니다. 소 번호는 늘 그렇듯 $1..N$입니다. $M$장($(1 \le M \le 100,000)$)을 찍었고 각 사진은 연속 구간을 담습니다. 사진 $i$는 소 $a_i$부터 $b_i$까지 양끝 포함입니다. 전체 사진이 모든 소를 담을 필요는 없습니다.

FJ는 모든 사진에 얼룩 있는 소가 정확히 한 마리씩 있음을 발견했습니다! 무리에 얼룩소가 있음을 알았지만 세어 보지는 않았습니다. 사진에 맞는 얼룩소의 최대 가능 수를 구하세요. 모든 사진과 일치하게 얼룩을 배정할 수 없다면 $-1$을 출력하세요.

입력

• $1$번 줄: 정수 $N$와 $M$.

• $2..M+1$번 줄: $i+1$번 줄은 $a_i$와 $b_i$입니다.

출력

• $1$번 줄: 얼룩소의 최대 가능 수, 해가 없으면 $-1$.

예제

입력 1

5 3
1 4
2 5
3 4

출력 1

1

참고

소 $5$마리와 사진 $3$장입니다. 첫 사진은 소 $1$부터 $4$까지이며 나머지도 같은 방식입니다.

마지막 사진에서 소 $3$ 또는 $4$가 얼룩소여야 함을 압니다. 어느 하나를 골라도 첫 두 사진도 만족합니다.

문제 출제자: Brian Dean, 2013