시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 46 18 13 35.135%

문제

그래프에서 체인이란 연속된 두 정점을 연결하는 간선이 존재하는 정점들의 나열이다. 이 때 한 정점이 여러 번 등장할 수도 있으며, 정점 하나도 체인이다.

사이클이 없는 방향 그래프가 주어질 때, 모든 정점을 포함시키기 위해서는 최소 몇 개의 체인이 필요한지 구하여라.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 10,000)과 간선의 개수 M (0 ≤ M ≤ 100,000)이 주어진다. 

둘째 줄부터 M개의 줄에 간선의 정보 u, v가 주어지며, u에서 v로 가는 간선이라는 의미이다.

입력으로 주어지는 그래프는 사이클이 없는 방향 그래프이다.

출력

모든 정점을 포함시키기 위해서는 필요한 체인 개수의 최소값을 출력한다.

예제 입력

7 11
1 2
1 5
2 5
2 3
2 7
3 4
3 6
4 6
5 4
5 6
7 3

예제 출력

2

힌트

예제: 2->7->3->6, 1->5->4

출처