Dynamic Centroid

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

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

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

첫 줄에 N이 주어진다. (2 ≤ N ≤ 5×105)

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

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