Description

在切完三色 $\Delta$ 和双色多边形之后，果果已经失去了辨别颜色的能力。这是，她看到了一棵单色的树。

于是果果决定遍历这棵树，她每遍历一个点，需要从起点出发，前往这个点，然后返回起点。特别地，在最后一个点的遍历中，她无需返回起点。

但是这棵树有着神奇的性质，使得果果每次从起点出发不能进入相同的子树内，即相邻两次遍历中，起点出发后经过的第一条边不能相同。

果果想要知道，对于树上的每个节点，如果选择该点作为起点，她最少要走多少路。如果从某个起点出发不能遍历整棵树，请你输出 -1。

Input Format

第一行包含一个整数 $n$ ($1 \le n \le 10^6$) ，表示树上节点的个数。 节点编号从 $1$ 到 $n$。
接下来 $n-1$ 行描述这棵树的结构，每行两个整数 $a, b$ ($1 \le a, b \le n$, $a \neq b$)，表示点 $a, b$ 间有一条连边。数据保证所有边构成一棵树。

Output Format

输出共 $n$ 行，第 $i$ 行描述以编号为 $i$ 的节点为起点的情况，对于第 $i$ 行：

• 如果以点 $i$ 为起点不能遍历整棵树，请输出 -1；
• 否则输出一行一个整数，表示从以点 $i$ 为起点的最小路程。

Sample

样例输入

9
3 6
2 4
2 6
2 5
1 7
2 7
8 9
7 8

样例输出

-1
23
-1
-1
-1
-1
-1
-1
-1

Hint

** Subtask #1 (5 points): $n \leq 20$ **
** Subtask #2 (7 points): $n \leq 100$ **
** Subtask #3 (18 points): $n \leq 2000$ **
** Subtask #4 (10 points): $n \leq 4 \times 10^4$ **
** Subtask #5 (14 points): $n \leq 10^5$ **
** Subtask #6 (21 points): $n \leq 5 \times 10^5$ **
** Subtask #7 (25 points): $n \leq 10^6$ **
** 友情提示：请注意输入输出效率。 **