사진

농부 존은 자신의 소 $N$마리($1 \le N \le 200{,}000$)를 한 줄로 세워 파노라마 사진을 만들려고 합니다. 소에는 $1$번부터 $N$번까지 번호가 매겨져 있습니다. 존은 사진을 $M$장($1 \le M \le 100{,}000$) 찍었는데, $i$번째 사진에는 $a_i$번부터 $b_i$번까지 연속한 구간의 소들이 담겨 있습니다($1 \le a_i \le b_i \le N$). 모든 소가 어떤 사진에든 반드시 담겨 있는 것은 아닙니다.

사진을 다 찍고 나서 존은 흥미로운 사실을 발견했습니다. 찍은 모든 사진에는 점박이 소가 정확히 한 마리씩 들어 있습니다. 존은 자신의 무리에 점박이 소가 몇 마리 있는지 정확히 세어 본 적이 없습니다. 사진들을 근거로, 무리에 존재할 수 있는 점박이 소의 최대 마리 수를 구하세요. 모든 사진과 모순 없이 점박이를 배정하는 방법이 전혀 없다면 $-1$을 출력합니다.

• 첫째 줄에 두 정수 $N$과 $M$이 주어집니다.
• 다음 $M$개의 줄 중 $i$번째 줄에는 $i$번째 사진이 담고 있는 구간의 양 끝 $a_i$와 $b_i$가 주어집니다.

• 점박이 소의 최대 마리 수를 한 줄에 출력합니다. 유효한 배정이 존재하지 않으면 $-1$을 출력합니다.

예시에는 소 $5$마리와 사진 $3$장이 있으며, 첫 번째 사진은 $1$번부터 $4$번 소를 담습니다. 세 번째 사진은 $3$번과 $4$번 소를 담으므로 그중 정확히 한 마리가 점박이여야 합니다. 둘 중 어느 쪽을 골라도 앞의 두 사진 조건까지 함께 만족되므로, 점박이 소는 최대 $1$마리입니다.