题目描述

有一天，Cool 先生建了一棵 $n$ 个点的树（没有环的无向连通图），他给任一编号 $i > 1$ 的点规定了两个值：$p_i < i$ 代表点 $i$ 的父节点，与 $w_i$ 代表 $i$ 与 $p_i$ 之间的边的边权。点 $1$ 是树根，所以它没有父节点。

你想知道 Cool 先生建的树长啥样，但是 Cool 先生拒绝告诉你，但他给了你一些提示：

他把所有的 $p_i$ 和 $w_i$ 值写成一列，得到了长为 $2 \cdot n - 2$ 的数列 $b$。

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

然后他将其随机打乱，得到了数列 $a$，并将 $a$ 告诉你。

然而只知道数列 $a$ 是无法还原那棵树的，你决定解决一个更难的问题。

定义一个树是 $k$ 长的，当且仅当点 $1$ 到点 $n$ 的路径上有恰好 $k$ 条边。

定义一个树是 $k$ 完美的，当且仅当这棵树是 $k$ 长的且点 $1$ 到点 $n$ 的路径上的边的边权之和是所有 $k$ 长的树中最大的。

你的任务是计算出每个 $k$ 值对应的 $k$ 完美的树中，点 $1$ 到点 $n$ 的路径上的边的边权之和。如果某个 $k$ 值不存在 $k$ 完美的树，则在该位置输出 $-1$。

输入格式

第一行包含一个整数 $n \ (2 \leq n \leq 10^5)$，代表树上的节点数。

第二行包含 $2 \cdot n -2$ 个整数 $a_1, a_2, \dots, a_{2n-2} \ (1 \leq a_i \leq n-1)$，代表数列 $a$ 中的数字。

输出格式

输出一行，共 $n-1$ 个空格隔开的整数 $w_1, w_2, w_3, \dots, w_{n-1}$，其中 $w_k$ 代表 $k$ 完美的树中点 $1$ 到点 $n$ 的路径上的边的边权之和。如果不存在 $i$ 长的树，则 $w_i=-1$。

3
1 1 2 2

2 3

3
2 2 2 2

-1 -1

6
1 4 5 4 4 4 3 4 4 2

-1 -1 -1 17 20

提示

第一个样例中，$1$ 完美的树由数列 $[1, 2, 1, 2]$ 构成（即，$p_2=1, w_2=2, p_3=1, w_3=2$），$2$ 完美的树由数列 $[1, 2, 2, 1]$ 构成（即，$p_2=1, w_2=2, p_3=2, w_3=1$）。以下是这两棵树的图形（点 $1$ 到点 $n$ 的路径上的边都为粗线）。

第二个样例中，不存在能通过重排 $a$ 构造出的 $k$ 完美的树。

第三个样例中，只有 $4$ 完美的和 $5$ 完美的树可以被构造出。它们分别由数列 $[1, 4, 2, 4, 3, 4, 4, 4, 4, 5]$ 和 $[1, 4,2, 4, 3, 4, 4, 4, 5, 4]$ 构成。以下是这两棵树的图形。