인기 있는 소들

면접 대비

시간 제한1초메모리 제한1024 MB

요약

방향 그래프의 간선 (A, B)는 소 A가 소 B를 인기 있다고 생각한다는 뜻이며, 모든 다른 소가 도달할 수 있는 소의 수를 구합니다.

난이도: 보통10점 중 5점
유형: 그래프, DFS, 위상 정렬
정답자: 아직 제출이 없습니다

문제

모든 소는 무리에서 가장 인기 있는 소가 되기를 꿈꾼다. 소가 $N$ 마리( $1 \le N \le 10{,}000$ )인 무리가 있고, 최대 $M$ 개( $1 \le M \le 50{,}000$ )의 순서쌍 $(A, B)$ 가 주어진다. 각 순서쌍은 소 $A$ 가 소 $B$ 를 인기 있다고 생각한다는 뜻이다. 인기는 推移적이다. 즉 $A$ 가 $B$ 를 인기 있다고 생각하고 $B$ 가 $C$ 를 인기 있다고 생각하면, 입력에 명시되지 않았더라도 $A$ 는 $C$ 도 인기 있다고 생각한다. 다른 모든 소가 인기 있다고 여기는 소의 수를 구하라.

입력

첫 줄에 공백으로 구분된 두 정수 $N$ 과 $M$ 이 주어진다. 이어지는 $M$ 개의 줄에는 각각 공백으로 구분된 두 정수 $A$ 와 $B$ 가 주어지며, 이는 소 $A$ 가 소 $B$ 를 인기 있다고 생각한다는 뜻이다.

출력

다른 모든 소가 인기 있다고 여기는 소의 수를 정수 하나로 출력한다.

힌트

3번 소만이 인기가 높은 소이다.

예제1

예제 1
입력
```
3 3
1 2
2 1
2 3
```
예상 출력
```
1
```