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

문제

하늘이의 부대에는 $1$번부터 $N$번까지 총 $N$개의 전화기가 있다. 각 전화기는 서로 다른 번호를 가지고 있으며, 다른 전화기로 착신 전환이 가능하다.

착신 전환이란 해당 전화기에 전화가 왔을 때 착신 전환의 대상이 되는 전화기가 대신 울리도록 하는 기능을 말한다. 착신 전환은 연속적으로 일어날 수 있어서 착신 전환된 전화가 또 다시 전환이 가능하며, 이렇게 전화를 타고 이동하다 착신 전환이 되어있지 않은 전화기를 만나면 해당 전화가 울리게 된다. 또한 최초 수신된 전화로부터 시작한 착신 번호의 이동 과정에서 이미 방문한 적이 있는 번호로 이동해야 한다면 더 이상 착신 전환을 진행하지 않고 해당 전화가 울리게 된다.

예를 들어 전화기 A, B, C가 있고 A $\to$ B $\to$ C $\to$ A로 착신 전환이 되어있다고 가정하자. 전화기 A에 전화를 걸면 A $\to$ B $\to$ C 순으로 이동하다가 이미 방문한 적 있는 전화기 A로 이동하지 않고 전화기 C가 최종적으로 울리게 되는 식이다.

호기심이 많은 하늘이는 각 전화별로 해당 전화기에 전화를 걸었을 때, 최종적으로 전화가 울리게 되는 전화기가 어떤 것인지 궁금해졌다. 하늘이를 도와 착신 전환 결과를 모두 구해주자.

입력

첫 번째 줄에 전화기의 개수 $N$이 주어진다. ($1 \leq N \leq 1,000,000$)

두 번째 줄에 $i$번 전화기가 착신 전환한 전화의 번호 $A_i$가 공백으로 구분되어 주어진다. ($1 \leq i \leq N$, $1 \leq A_i \leq N$)

이때 착신 전환이 되어있지 않은 전화는 $A_i = i$로 주어진다.

출력

첫 번째 줄에 $1$번부터 $N$번 전화기에 전화를 걸었을 때 최종적으로 울리게 되는 전화의 번호를 차례대로 공백으로 구분하여 출력한다.

예제 입력 1

5
1 2 5 4 5

예제 출력 1

1 2 5 4 5

예제 입력 2

5
2 3 4 5 1

예제 출력 2

5 1 2 3 4

예제 입력 3

5
2 3 4 2 3

예제 출력 3

4 4 2 3 2

출처

Contest > 보라매컵 > 제6회 보라매컵 C번