Problem Description

One day, Mr. Cool constructed a tree with \( n \) nodes (a connected undirected graph without cycles), and he assigned two values to any node with the number \( i > 1 \): \( p_i < i \) representing the parent node of node \( i \), and \( w_i \) representing the edge weight between node \( i \) and \( p_i \). Node 1 is the root, so it has no parent node.

You want to know what Mr. Cool's tree looks like, but he refuses to tell you. However, he gives you a hint:

He wrote down all the \( p_i \) and \( w_i \) values in a sequence, resulting in a sequence \( b \) of length \( 2 \cdot n - 2 \).

\[ b = [p_2, w_2, p_3, w_3, \dots, p_{n-1}, w_{n-1}, p_n, w_n] \]

Then he shuffled it randomly to get the sequence \( a \), which he tells you.

However, knowing only the sequence \( a \) is not enough to reconstruct the tree, so you decide to tackle a harder problem.

A tree is defined as \( k \)-long if and only if there are exactly \( k \) edges on the path from node 1 to node \( n \).

A tree is defined as \( k \)-perfect if it is \( k \)-long and the sum of the edge weights on the path from node 1 to node \( n \) is the largest among all \( k \)-long trees.

Your task is to calculate the sum of the edge weights on the path from node 1 to node \( n \) for each \( k \)-perfect tree corresponding to each \( k \) value. If there is no \( k \)-perfect tree for a certain \( k \), output \(-1\) at that position.

Input Format

The first line contains an integer \( n \ (2 \leq n \leq 10^5) \), representing the number of nodes in the tree.

The second line contains \( 2 \cdot n - 2 \) integers \( a_1, a_2, \dots, a_{2n-2} \ (1 \leq a_i \leq n-1) \), representing the numbers in sequence \( a \).

Output Format

Output one line with \( n-1 \) space-separated integers \( w_1, w_2, w_3, \dots, w_{n-1} \), where \( w_k \) represents the sum of the edge weights on the path from node 1 to node \( n \) in the \( k \)-perfect tree. If there is no \( i \)-long tree, then \( w_i = -1 \).

Sample Input and Output

Sample Input #1

3
1 1 2 2

Sample Output #1

2 3

Sample Input #2

3
2 2 2 2

Sample Output #2

-1 -1

Sample Input #3

6
1 4 5 4 4 4 3 4 4 2

Sample Output #3

-1 -1 -1 17 20

Notes

In the first sample, the \( 1 \)-perfect tree is constructed from the sequence \([1, 2, 1, 2]\) (i.e., \( p_2 = 1, w_2 = 2, p_3 = 1, w_3 = 2 \)), and the \( 2 \)-perfect tree is constructed from the sequence \([1, 2, 2, 1]\) (i.e., \( p_2 = 1, w_2 = 2, p_3 = 2, w_3 = 1 \)). The following are the graphs of these two trees (the edges on the path from node 1 to node \( n \) are bold).

In the second sample, there is no \( k \)-perfect tree that can be constructed by rearranging \( a \).

In the third sample, only the \( 4 \)-perfect and \( 5 \)-perfect trees can be constructed. They are constructed from the sequences \([1, 4, 2, 4, 3, 4, 4, 4, 4, 5]\) and \([1, 4, 2, 4, 3, 4, 4, 4, 5, 4]\), respectively. The following are the graphs of these two trees.

见题面 Input 部分

见题面 Output 部分