레이팅 미적용설명
농부 존(Farmer John)은 편의상 1..N으로 번호가 붙은 N마리 (1 <= N <= 200,000)의 소들이 줄지어 선 파노라마 사진을 조립하기로 했다. 이를 위해 존은 M장 (1 <= M <= 100,000)의 사진을 찍었으며, 각 사진은 연속한 범위의 소들을 담고 있다. 사진 i는 소 a_i부터 b_i까지(양 끝 포함)를 담는다. 사진들을 모두 합쳐도 모든 소를 반드시 담지는 않을 수 있다.
사진을 찍은 후, FJ는 아주 흥미로운 현상을 발견했다. 자신이 찍은 각 사진에 반점이 있는 소가 정확히 한 마리씩 담겨 있는 것이다! FJ는 무리에 반점 있는 소가 몇 마리 있다는 것은 알고 있었지만, 실제로 세어 본 적은 없었다. 사진들을 바탕으로, 무리에 존재할 수 있는 반점 있는 소의 최대 수를 구하시오. FJ의 사진 결과와 일치하는 반점 배정이 불가능하면 -1을 출력한다.
제약
입력 형식
첫째 줄: 두 정수 N과 M.
둘째 줄부터 M+1번째 줄까지: i+1번째 줄에 a_i와 b_i가 주어진다.
출력 형식
FJ의 농장에 있을 수 있는 반점 있는 소의 최대 수, 가능한 해가 없으면 -1.
Standard input / output
This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:
입력을 읽을 파일
photo.in · 출력을 쓸 파일 photo.out예제 1
입력
5 3
1 4
2 5
3 4출력
1설명
Output details: From the last photo, either cow 3 or cow 4 must be spotted; choosing either satisfies the first two photos as well.
문제 정보
태그