트리 순열

옛날 옛적에 Mr. Cool이 n개의 정점으로 이루어진 트리(사이클이 없는 무방향 그래프)를 만들었다. 각 정점 i (i > 1)에 대해 두 수를 골랐다. 하나는 정점 i의 직접적인 부모인 p_i (p_i < i)이고, 다른 하나는 정점 i와 p_i를 잇는 간선의 가중치 w_i이다. 정점 1은 루트이므로 부모가 없다.

Mr. Cool은 이 수들을 모두 한 줄에 적었다. 그렇게 얻은 길이 $2n-2$의 배열을 b라고 하면 b = [p_2, w_2, p_3, w_3, ..., p_n, w_n]이다. 이후 b를 무작위로 섞어 배열 a를 만들고, 그 a를 여러분에게 주었다.

a의 값만으로는 트리를 복원할 수 없으므로, 다른 문제를 풀어야 한다. 정점 1과 정점 n 사이 경로 위의 간선이 정확히 k개인 트리를 k-long 트리라고 한다. k-long 트리 중에서 정점 1과 정점 n 사이 경로의 가중치 합이 최대인 트리를 k-perfect 트리라고 한다. Mr. Cool이 a를 재배열해 만들 수 있는 k-long 트리들 가운데에서 고른다.

1부터 n-1까지의 각 k에 대해 k-perfect 트리의 경로 가중치 합을 출력하라. 만들 수 있는 k-long 트리가 없으면 -1을 출력한다.

첫 번째 줄에 정점의 개수 n ($2 \le n \le 10^5$)이 주어진다. 두 번째 줄에는 배열 a의 원소 $2n-2$개 $a_1, a_2, \ldots, a_{2n-2}$ ($1 \le a_i \le n-1$)가 주어진다.

한 줄에 공백으로 구분된 정수 $w_1, w_2, \ldots, w_{n-1}$을 출력한다. $w_k$는 k-perfect 트리에서 정점 1과 정점 n 사이 경로의 가중치 합이다. k-long 트리가 없으면 $w_k = -1$이다.

그림에서 굵은 선은 정점 1에서 정점 n까지의 경로를 나타낸다.