데이터의 비참한 손실
시간 제한6초메모리 제한512 MB
N개 강의의 충돌 그래프가 주어질 때, 구간 그래프로 실현 가능한 최소 색칠 수, 즉 필요한 최소 강의실 수를 구한다.
문제
경쟁 프로그래밍 대학(UCP)의 강의실 배정 시스템에 심각한 문제가 발생해 대량의 데이터가 손실됐다. 강의실 배정 시스템의 임무는 강의에 강의실을 배정하는 것이다. 안타깝게도 이 작업을 수행하도록 구현된 알고리즘이 완전히 폭주해 매우 난해한 오류 메시지를 출력하기 시작했다. 아무도 그 오류 메시지를 해독하지 못했지만, 모두 그것이 매우 길고 화려하며 몰입감 있는 일종의 증명인 것 같다고 입을 모은다. 다행히 일부 정보는 복구됐다.
복구된 데이터에서 오늘 N개의 강의가 있고, 각 강의는 하나의 연속된 시간 구간을 차지한다는 것을 알아냈다. 일부 강의는 겹칠 수 있는데, 이는 시간 구간이 교차함을 뜻한다. 안타깝게도 각 강의가 필요로 하는 시간 구간을 설명하는 정보는 손실됐다! 다행히 어떤 강의 쌍이 겹치는지는 알아낼 수 있었다.
두 강의가 겹치면 서로 다른 강의실에 배정해야 한다. UCP에는 강의실 수가 제한되어 있고, 모든 강의에 강의실을 배정해야 한다. 곧 사람들이 강의를 들으러 오기 시작할 것이다. 모든 강의를 배정할 수 있는 최소 강의실 수를 구할 수 있겠는가?
입력
첫 번째 줄에는 강의의 수 N (1 ≤ N ≤ 200 000)과 겹치는 쌍의 수 M (0 ≤ M ≤ 200 000)이 주어진다.
다음 M개의 줄은 겹치는 쌍을 설명한다. 각 줄에는 두 정수 u와 v (1 ≤ u < v ≤ N)가 주어지며, 이는 서로 겹치는 강의 쌍을 나타낸다. 주어진 M개의 겹침을 정확히 갖는 N개의 강의 집합이 존재함이 보장된다. 각 겹침은 유일하며 입력에 정확히 한 번 나타난다.
출력
필요한 최소 강의실 수를 출력한다.