18133번 - 가톨릭대학교에 워터 슬라이드를??

문제

치삼이는 축제를 맞아 가톨릭대학교에 건물 옥상에서 다른 건물 옥상으로 이동하는 워터 슬라이드를 짓기로 했다!

가톨릭대학교의 건물은 총 N 개로 이루어져 있으며, 편의상 1번 건물부터 N 번 건물까지 있다고 하자. 이 건물들의 옥상과 옥상 사이에 터널이 설치되어 있다면 터널을 따라 연결된 건물 옥상으로 물이 흐른다. 단 터널은 방향이 정해져 있어 주어진 방향으로만 물이 흐를 수 있으며, 이동할 수 있는 모든 건물 옥상으로 물이 흐른다. 예를 들어 1에서 2번으로 향하는 터널이 있고, 2에서 3번으로 향하는 터널이 있다면, 1번에 물을 붓는다면 2번과 3번 건물 옥상에도 물이 흘러간다는 의미이다. 또한, 두 옥상 사이의 터널이 여러 개가 있을 수 있으며, 하나의 건물 옥상에서 그 건물 옥상으로 연결되는 터널은 없다.

모든 터널은 설치가 완료되었고, 내일이 축제이므로 치삼이는 이제 양동이를 구입해 물을 흘려보내 워터 슬라이드를 완성하려고 한다! 하나의 양동이로는 하나의 건물 옥상에만 물을 부을 수 있고, 양동이는 상상할 수 없을 만큼 충분히 크기 때문에, 물을 부으면 터널을 타고 흐를 수 있는 모든 건물 옥상으로 전달된다. 하지만 양동이가 너무 비싼 관계로 치삼이는 양동이의 구매를 최소화하려고 한다.

여러분이 치삼이를 도와 최소 몇 개의 양동이로 모든 건물 옥상에 물을 흘려보낼 수 있는지 구해주자!

입력

두 정수 N (2 ≤ N ≤ 100,000), M (1 ≤ M ≤ 100,000)이 주어진다. N 은 건물의 개수를, M 은 터널의 개수를 나타낸다. 건물 옥상들의 번호는 1과 N 사이의 정수다.

다음 M개의 줄에는 각각 두 정수 x, y (1 ≤ x, y ≤ N)가 주어지는데, 이는 x 번 건물 옥상에서 y 번 건물 옥상으로 향하는 터널이 설치되어있음을 뜻한다.

출력

모든 건물 옥상에 물을 흘려보내기 위해 최소한으로 필요한 양동이 개수를 출력한다.

제한

힌트