很久以前，Mr. Cool 创建了一棵包含 $n$ 个顶点的树（无环无向图）。他为每个顶点 $i > 1$ 指定了两个数字：$p_i < i$（顶点 $i$ 的直接祖先）以及 $w_i$（顶点 $i$ 与 $p_i$ 之间边的权重）。顶点 1 是根节点，因此它没有祖先。

你想知道 Mr. Cool 构建了什么样的树，但他拒绝告诉你，只给了你一个提示： 他将所有这些数字写在了一行中。这样他就得到了一个长度为 $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$ 的值无法还原这棵树，你决定解决一个不同的问题。

如果从顶点 1 到顶点 $n$ 的路径上恰好有 $k$ 条边，我们称这棵树为 $k$-长树。 如果一棵树是 $k$-长树，且从顶点 1 到顶点 $n$ 的路径上所有边的权重之和在所有可能的 $k$-长树中达到最大，我们称这棵树为 $k$-完美树。

你的任务是输出所有可能的 $k$-完美树中，从顶点 1 到顶点 $n$ 的路径上的权重之和。如果某种 $k$-长树无法由 Mr. Cool 构建，则输出 $-1$。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 10^5$)，表示树中顶点的数量。 第二行包含 $2 \cdot n - 2$ 个整数 $a_1, a_2, \dots, a_{2n-2}$ ($1 \le a_i \le n - 1$)，即数组 $a$ 的元素。

输出格式

在一行中输出 $n - 1$ 个空格分隔的整数 $w_1, w_2, w_3, \dots, w_{n-1}$，其中 $w_k$ 表示 $k$-完美树中从顶点 1 到顶点 $n$ 的路径权重之和。如果不存在 $k$-长树，则 $w_k$ 应为 $-1$。

样例

输入 1

3
1 1 2 2

输出 1

2 3

输入 2

3
2 2 2 2

输出 2

-1 -1

输入 3

6
1 4 5 4 4 4 3 4 4 2

输出 3

-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-完美树和 2-完美树的示意图（从顶点 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]$ 定义。以下是它们的示意图：