지역

빅뱅국에는 1번부터 N번까지 번호가 붙은 N개의 도시가 있다.

도로는 두 종류이다. 먼저 고속 도로가 N-1개 있으며, 각 i(1 ≤ i < N)에 대해 i번 도시에서 i+1번 도시로 가는 도로가 하나씩 있다. 여기에 몇 개의 일반 도로가 추가로 있을 수 있다. 일반 도로도 방향이 있으며, 입력으로 주어지는 Si Ei는 Si번 도시에서 Ei번 도시로 가는 도로를 뜻한다.

이 나라의 모든 도시를 몇 개의 지역으로 나누려고 한다. 모든 도시는 정확히 하나의 지역에 속해야 하며, 각 지역은 같은 수의 도시를 가져야 한다. 서로 다른 두 지역 A와 B에 대해, A에 속한 어떤 도시에서 B에 속한 어떤 도시로 가는 경로가 존재한다면, B에 속한 어떤 도시에서도 A에 속한 어떤 도시로 가는 경로가 존재해서는 안 된다.

도시 수 N, 일반 도로 수 M, 그리고 일반 도로 정보가 주어졌을 때 만들 수 있는 지역 수의 최댓값을 구하시오.

첫째 줄에 도시의 개수 N과 일반 도로의 개수 M이 주어진다.

둘째 줄부터 M개의 줄에 일반 도로 정보가 하나씩 주어진다. 각 줄에는 Si Ei가 주어지며, 이는 Si번 도시에서 Ei번 도시로 가는 일반 도로를 의미한다.

입력으로 주어지는 일반 도로 정보는 중복되지 않는다.

만들 수 있는 지역 수의 최댓값을 출력한다.

• 1 ≤ N ≤ 3,000
• 1 ≤ M ≤ 1,000
• 1 ≤ Si, Ei ≤ N
• Si ≠ Ei
• Ei ≠ Si + 1