Byteotian Railways (BR) 的铁路网由连接某些车站对的双向轨道组成。每对车站之间最多由一段轨道连接。此外，从任意一个车站到其他所有车站都有且仅有一条路径。（路径可能由多段轨道组成，但不能重复经过任何车站。）

Byteasar 是 BR 的一名卧底检查员。他的工作是选择一个车站（记为 $S$）作为行动中心，并前往所有其他车站。他的行程应遵循以下规则：

• Byteasar 从车站 $S$ 出发。
• 接下来，他选择一个尚未检查的车站，沿最短路径（当然是乘火车）前往该站，检查完毕后返回 $S$。
• BR 的腐败员工会互相通报 Byteasar 的行踪。为了迷惑他们，Byteasar 在选择下一个要检查的车站时，必须确保出发方向与上一次不同，即沿 $S$ 出发的不同轨道段前往。
• 每个车站（$S$ 除外）必须且仅能被检查一次。
• 在检查完最后一个车站后，Byteasar 不必返回 $S$。

每段轨道的行程时间相同：一小时。

Byteasar 打算考虑将所有车站作为初始车站 $S$。对于每一个车站，他想知道在可能的情况下，检查剩余车站的最小总行程时间；如果对于某个特定的 $S$ 无法完成检查，则输出相应结果。

输入格式

输入的第一行包含一个整数 $n$ ($1 \le n \le 1\,000\,000$)，表示车站的数量。车站编号从 $1$ 到 $n$。接下来的 $n-1$ 行描述了轨道段，每行包含两个整数 $a, b$ ($1 \le a, b \le n, a \neq b$)，由空格分隔，表示车站 $a$ 和 $b$ 之间有一段轨道。每段轨道在描述中仅出现一次。

在至少占 $30\%$ 分值的测试点中，满足 $n \le 2\,000$。

输出格式

程序应在标准输出中打印 $n$ 行，每行包含一个整数。第 $i$ 行的整数应为当 $S=i$ 时 Byteasar 检查所有车站所需的最短行程时间（以小时为单位）；如果对于 $S=i$ 无法完成所有车站的检查，则第 $i$ 行应输出 $-1$。

样例

样例输入 1

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

样例输出 1

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

该图展示了样例中指定的铁路网。只有当 $S=2$ 时，才有可能检查所有车站。一种最优的检查顺序是：7, 4, 8, 6, 1, 5, 3, 9。这会导致总行程时间为 23 小时。