농장에서 사탕 모으기

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

요약

각 칸마다 다음 칸을 가리키는 포인터가 하나씩 있다. 모든 시작 칸에 대해, 이미 방문한 칸에 다시 도달할 때까지 방문하는 서로 다른 칸의 수를 구한다.

난이도: 보통10점 중 6점
유형: 그래프, DFS, 구현, 배열
정답자: 아직 제출이 없습니다

문제

위스콘신의 소들은 매년 미국의 가을 명절인 핼러윈을 기념하기 위해 의상을 차려입고, 농부 존이 편의상 $1 \dots N$ 으로 번호를 매긴 $N$ 개( $1 \le N \le 100{,}000$ )의 축사에 놓아둔 사탕을 모은다.

헛간이 그리 넓지 않기 때문에, 존은 소들이 더 오래 즐길 수 있도록 소들이 따라야 할 이동 경로를 지정한다. 존은 각 축사 $i$ 에 '다음 축사 번호' $next_i$ ( $1 \le next_i \le N$ )를 붙여 두어, 소가 그 축사 다음에 어느 축사로 가야 하는지를 알려 준다. 그래서 소들은 사탕을 모으기 위해 헛간을 여러 번 오갈 수도 있다.

소 $i$ 는 반드시 축사 $i$ 에서 사탕 모으기를 시작한다. 소는 이미 방문했던 축사에 다시 도착하는 순간 사탕 모으기를 멈춘다.

각 소가 사탕 모으기를 멈추기 전까지 방문하는 서로 다른 축사의 개수를 구하여라.

입력

첫째 줄: 정수 $N$ .
둘째 줄부터 $N+1$ 번째 줄까지: $i+1$ 번째 줄에 정수 $next_i$ 하나.

출력

첫째 줄부터 $N$ 번째 줄까지: $i$ 번째 줄에 소 $i$ 가 이전에 방문한 축사로 다시 돌아오기 전까지 방문하는 서로 다른 축사의 총 개수를 출력한다.

예제3

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