케이크 배달

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

요약

마을 1에서 시작하는 보행으로 모든 마을을 방문해야 할 때 필요한 최소 보행 수를 구하는 문제다.

난이도: 보통10점 중 7점
유형: 그래프, 동적 계획법, 그리디, 최단 경로
정답자: 아직 제출이 없습니다

문제

미르코는 마을에서 가장 맛있는 케이크를 만든다. 자몽을 올린 치즈케이크다. 자기 조리법을 알리려고 미르코는 자기 군에 있는 $N$ 개 마을마다 케이크를 최소 한 개씩 나눠 주기로 했다. 이 일에 판매원을 여러 명 고용한다. 판매원은 케이크를 원하는 만큼 들고 다니고, 마을을 잇는 일방통행 도로를 따라 이동하면서 케이크를 나눠 준다.

판매원은 모두 미르코의 마을에서 출발하고, 그 마을의 번호는 1번이다. 고용한 판매원의 경로는 미르코가 정한다. 경로는 도로를 이어 붙인 임의의 순서이고, 같은 마을을 여러 번 지나도 된다. 한 걸음도 움직이지 않는 판매원도 있어도 되며, 그 판매원은 1번 마을에만 케이크를 준다.

모든 마을이 케이크를 받게 하려면 미르코는 판매원을 최소 몇 명 고용해야 하는가?

입력

첫째 줄에 마을의 수 $N$ 과 도로의 수 $E$ 가 주어진다. ( $1 \le N \le 500$ , $1 \le E \le 50000$ )

다음 $E$ 개 줄에는 각각 두 정수 $A$ 와 $B$ 가 주어진다. ( $1 \le A, B \le N$ ) 마을 $A$ 에서 마을 $B$ 로 가는 일방통행 도로가 있다는 뜻이고, 판매원은 이 도로로 마을 $A$ 에서 마을 $B$ 로 곧바로 갈 수 있다.

같은 도로가 여러 번 주어질 수 있고, $A$ 와 $B$ 가 같을 수도 있다.

출력

첫째 줄에 미르코가 고용해야 하는 판매원의 최소 인원을 출력한다. 모든 마을이 케이크를 받는 방법이 항상 존재하는 입력만 주어진다.

예제3

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