동적 센트로이드

크기 $N$의 트리에서, 센트로이드란 정점을 기준으로 나누어지는 서브트리의 크기가 모두 $N/2$ 이하인 정점을 뜻한다. 어떠한 트리라도 센트로이드가 존재함이 알려져있다.

1번 정점이 트리의 루트이며, $i$번 정점의 부모는 $p_i$이고, $p_i < i$이다.

$1$부터 $N$까지의 $k$에 대해, 1번 정점부터 $k$번 정점까지만 사용한 트리의 센트로이드를 구하여라.

첫 줄에 $N$이 주어진다. ($2 \le N \le 5 \times 10^5$)

둘째 줄에 $i = 2$부터 $i = N$까지, $p_i$가 공백으로 구분되어 주어진다. ($1 \le p_i < i$)

$1$부터 $N$까지의 $k$에 대해, 1번 정점부터 $k$번 정점까지만 사용한 트리의 센트로이드의 번호를 공백으로 구분하여 순서대로 출력한다. 여러가지의 답이 존재한다면 그 중 가장 작은 것을 출력한다.