시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 84 21 18 26.866%

문제

김형택이 통치하는 빅뱅국은 N개의 도시로 이루어져 있다. 김형택은 초창기에는 탑시, 지용시, 지드래곤시, 승리시, 대성시, 태양시와 같은 이름을 붙였지만, 옆 나라 소시국 (국왕 : 오민식)의 도시 이름을 이길 수 없어서 도시의 이름을 1번부터 N번까지로 바꿨다.

김형택의 국가에는 두 가지 종류의 도로가 있는데, 하나는 일반 도로이고, 또 다른 하나는 고속 도로이다. 고속 도로는 N-1개가 있으며, 1번에서 2번으로 가는 도로, 2번에서 3번으로 가는 도로, i번에서 i+1번으로 가는 도로, N-1번에서 N번으로 가는 도로와 같이 총 N-1개가 있다. 그리고, 몇 개의 일반 도로가 따로 있을 수 있다.

김형택은 이 나라를 몇 개의 지역으로 나누려고 한다. 그리고, 가능하면 많은 지역을 만드려고 한다. 각각의 지역은 모두 같은 수의 도시를 가지고 있어야 하고, 모든 도시는 단 하나의 지역에 속해야 한다. 지역으로 나눌 때에는 다음과 같은 조건을 만족해야 하는데, 지역 A와 지역 B가 다른 지역이라고 가정할 때, A에 속해 있는 어떤 도시에서 B에 속해 있는 어떤 도시로 가는 경로가 있다면, B에 속해 있는 어떤 도시에서 A에 속해 있는 어떤 도시로 가는 경로는 없어야 한다.

입력으로 도시의 개수 N개와 일반 도로의 개수 M개와 그 도로가 주어졌을 때, 김형택이 나눌 수 있는 지역의 개수의 최댓값을 구하는 프로그램을 작성하시오. (일반 도로도 도로다. 고속 도로도 도로다.)

입력

첫째 줄에 도시의 개수 N과 일반 도로의 개수 M이 주어진다. 둘째 줄부터 한 줄에 하나씩 일반 도로의 정보가 주어진다. 일반 도로의 정보는 S E와 같이 주어지며, S에서 E로 가는 일반 도로라는 뜻이다. N은 3,000보다 작거나 같은 자연수이다. M은 1,000보다 작거나 같은 자연수이다.

출력

김형택이 나눌 수 있는 지역의 최댓값을 출력한다.

예제 입력

6 3
2 1
3 2
6 4

예제 출력

2

힌트

출처