산책하는 소

면접 대비

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

요약

각 목장에서 나가는 길이 하나뿐인 그래프에서, 같은 목장으로 돌아오는 사이클 중 가장 많은 목장을 지나는 길이를 구합니다.

난이도: 쉬움10점 중 3점
유형: 그래프, 위상 정렬
정답자: 아직 제출이 없습니다

문제

소들은 저녁을 먹으러 외양간에 가기 전, 해가 지는 것을 보면서 $N$ 개( $1 \le N \le 30,000$ )의 목초지를 산책하는 것을 좋아한다. 각 목초지는 정확히 하나의 목초지로 이어지지만, 여러 목초지에서 들어오는 경로가 있는 목초지도 있다. 올바른 산책에서 소는 아무 목초지에서나 출발할 수 있고, 같은 목초지에서 끝나야 하며, 다른 목초지를 두 번 방문해서는 안 된다. 목초지 사이의 경로가 주어졌을 때, 소가 할 수 있는 가장 긴 올바른 산책을 구하라.

입력

첫 줄에는 정수 $N$ 이 주어진다. 둘째 줄부터 $N+1$ 번째 줄까지 $M$ 번째 줄에는 목초지 $M-1$ 이 연결된 목초지의 번호가 주어진다. 즉, 둘째 줄에는 목초지 1에서 갈 수 있는 목초지가 주어진다.

출력

올바른 산책에서 방문할 수 있는 목초지의 최대 개수를 한 줄에 출력한다.

예제1

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