개의 정점과 개의 간선으로 이루어진 유향 단순 그래프가 주어진다.
정점 에서 출발해 사이클을 방문할 수 있다는 것은, 에서 출발하여 간선을 따라 이동했을 때 어떤 사이클에 포함된 정점에 도달할 수 있다는 뜻이다.
정점들 중, 해당 정점에서 출발해 사이클을 방문할 수 없는 정점의 개수를 구하여라.
Input
입력은 다음과 같은 형식으로 주어진다.
간선 는 번 정점에서 번 정점으로 가는 간선을 의미한다.
Output
사이클을 방문할 수 없는 정점의 개수를 출력한다.
Constraints
- .
- .
- ().
- ().
- 같은 방향의 간선이 두 번 이상 주어지지 않는다.
Subtasks
Samples
예제 1
입력
4 3
1 2
2 3
3 4
출력
4
그래프에 사이클이 없으므로 모든 정점에서 사이클을 방문할 수 없다.
예제 2
입력
6 5
1 2
2 3
3 2
4 1
5 6
출력
2
정점 와 은 사이클에 포함되어 있다. 정점 과 에서는 이 사이클을 방문할 수 있다.
정점 와 에서는 어떤 사이클도 방문할 수 없으므로 답은 이다.
예제 3
입력
5 6
1 2
2 3
3 1
3 4
4 5
5 4
출력
0
모든 정점에서 어떤 사이클을 방문할 수 있다.