광고 (Advertisement)

JOI 사는 마침내 신제품 "터무니없이 기묘한 도구 (Incredibly Odd Instrument)"의 개발을 끝냈다. 사장은 이 신제품에 대한 안내를 구매가 예상되는 모든 사람에게 보낼 생각으로 그들의 연락처를 입수했지만, 너무 많은 사람에게 안내를 보내면 악질 업자로 의심받을 수 있다는 사실을 깨달았다.

그래서 가능한 한 적은 수의 사람을 골라 안내를 보내고, 입소문으로 모든 사람이 신제품에 대해 알게 하려 한다. 신제품이 매우 혁신적이므로 제품에 대해 알게 된 사람은 곧 자신이 연락처를 아는 모든 사람에게 신제품 정보를 알린다고 생각할 수 있다.

구매가 예상되는 모든 사람에게 신제품 정보가 퍼지게 하려면 몇 명의 사람에게 안내를 보내야 하는지 구하는 프로그램을 작성하시오.

입력의 첫째 줄에는 두 정수 n, m (1 ≤ n ≤ 100 000, 0 ≤ m ≤ 100 000)이 공백으로 구분되어 쓰여 있다. n은 신제품 구매가 예상되는 사람의 수를 나타낸다.

이어지는 m개의 줄 (2번째 줄부터 m + 1번째 줄)은 어느 사람이 어느 사람의 연락처를 아는지를 나타낸다. j + 1번째 줄 (1 ≤ j ≤ m)에는 두 정수 a_j, b_j (1 ≤ a_j, b_j ≤ n, a_j ≠ b_j)가 공백으로 구분되어 쓰여 있다. 이는 사람 a_j가 사람 b_j의 연락처를 아는 것을 나타낸다. 사람은 1부터 n까지의 정수로 나타낸다. j ≠ k이면 a_j = a_k이고 b_j = b_k인 경우는 없다.

출력은 표준 출력으로 한다. 안내를 보낼 상대의 수의 최솟값을 나타내는 정수 하나를 출력하시오.