题目描述

Byteasar 是 Byteoian Railways 的一名便衣巡视员。BR 的铁路架构是一棵 $N$ 个节点的树，Byteasar 需要检查所有的N个节点。他按照如下方式行动：

• 首先选定一个行动中心 $S$，并且检查 $S$。

• 从 $S$ 出发前往任意一个未检查的点（沿树上两点的唯一最短路走），检查该节点，然后返回 $S$。特别地，检查完最后一个节点后不需要返回。

检查节点不需要时间，走过一条路的时间为 $1$。

为了不暴露身份，Byteasar 规定相邻两次检查所经过的道路不允许有重复。

也就是说，除第一次检查之外，他每次从 $S$ 出发走过的第一条边不能和上一次出发相同。

输入格式

第一行是一个整数 $N$。

接下来 $N-1$ 行每行有 $2$ 个整数 $A,\ B$，表示 $A$ 和 $B$ 之间有一条边。

输出格式

$N$ 行，第 $I$ 行表示如果以 $I$ 作为行动中心，Byteasar 检查完所有车站需要的最小时间。如果不可能做到，该行输出 $-1$。

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

数据规模与约定

对于 $30\%$ 的数据，$1\leq n\leq 2\times 10^3$。

对于 $100\%$ 的数据，$1\leq n\leq 10^6$，$1\leq A,\ B\leq N$。

题目来源

鸣谢 Object022。