레이팅 미적용설명
FJ는 한 줄로 서서 편의상 1..N으로 번호가 붙은 N마리 (2 <= N <= 1,000,000,000)의 소들의 사진을 찍고 싶어 한다. 각 사진은 줄에서 연속한 범위의 소들을 담을 수 있으며, FJ는 모든 소가 적어도 한 장의 사진에 나오게 하고 싶다.
안타깝게도 사이가 나쁜 소 쌍이 K쌍 (1 <= K <= 1000) 있는데, 이들은 각각 같은 사진에 찍히기를 거부한다. 사이가 나쁜 쌍들의 위치가 주어질 때, FJ가 찍어야 하는 사진의 최소 수를 구하시오.
제약
입력 형식
첫째 줄: 공백으로 구분된 두 정수 N과 K.
둘째 줄부터 K+1번째 줄까지: i+1번째 줄에 두 정수 A_i와 B_i가 주어지며, 위치 A_i와 B_i의 소들이 사이가 나빠서 같은 사진에 찍힐 수 없음을 나타낸다.
출력 형식
FJ가 찍어야 하는 사진의 최소 수를 나타내는 정수 하나.
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
입력
7 3
1 3
2 4
5 6출력
3설명
Output details: FJ can take 3 photos: 1-2, 3-5, and 6-7.
문제 정보
riseoj 작성
출처 올림피아드 > USACO > 2012-2013 > US Open > Bronze
태그