시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB28617716263.529%

문제

학교에 입학하여 설레는 첫 등굣길, 당신은 신촌에서 길을 잃어버렸다. 신촌은 $N$개의 장소로 이루어져 있고, 이대는 $N$번 장소에 존재한다.

당신은 현재 장소에 있는 행인에게 길을 묻는 것을 반복하여 이대에 도착하려고 한다. $i$번 장소에서 행인에게 길을 물으면 $A_i$번 장소를 가리키며 "이대로 가시면 돼요." 라고 대답한다. 당신은 $A_i$번 장소로 이동한다.

$f(i)$를 $i$번 장소에서 출발한다고 했을 때 이대에 도착하기 위한 최소 질문 수라고 하자. 만약 아무리 많은 질문을 하여도 도착할 수 없다면 $-1$이다.

모든 장소에 대하여 $f(i)$를 구해보자.

입력

첫째 줄에 신촌의 장소의 수를 나타내는 $N$이 주어진다. ($1 \leq N \leq 200\,000$)

둘째 줄에 $1, 2, \cdots, N$번 장소에서 길을 물었을 때 행인이 가리키는 장소를 나타내는 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. ($1 \leq A_i \leq N$)

출력

$i$번째 줄에 $f(i)$를 출력한다.

예제 입력 1

5
2 1 5 3 2

예제 출력 1

-1
-1
1
2
0