농장에서 사탕 모으기

위스콘신의 소들은 매년 미국의 가을 명절인 핼러윈을 기념하기 위해 의상을 차려입고, 농부 존이 편의상 $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$가 이전에 방문한 축사로 다시 돌아오기 전까지 방문하는 서로 다른 축사의 총 개수를 출력한다.