说明

有 $N$ 只松鼠在一棵树上储存橡果。这棵橡树也是一棵图论意义上的树：它是一张有 $N$ 个顶点（编号从 $1$ 到 $N$）和 $N-1$ 条无向边的连通图。每只松鼠位于树中一个不同的顶点上，如果两只松鼠所在的顶点之间有一条边相连，则称它们为 邻居。

按照顶点编号从小到大的顺序，从编号为 $1$ 的顶点上的松鼠开始，每只松鼠会从它当前拥有橡果数量最多的那个邻居那里偷走 $1$ 颗橡果。如果有多个邻居同时拥有最多的橡果数量，那么这只松鼠会从这些邻居中 每只 都偷走 $1$ 颗橡果！

为了限制这些恶作剧造成的损失，你希望给松鼠分配橡果，使得初始时每只松鼠至少有 $N$ 颗橡果（这样没有松鼠会因为被偷而耗尽橡果），并且在所有 $N$ 只松鼠都完成偷窃之后，每只松鼠最终拥有的橡果数量与它最初拥有的数量相同。可以证明，存在一种分配方案使得每只松鼠初始最多拥有 $2N-1$ 颗橡果。请找出任意一种满足这些条件的分配方案。

输入格式

输入的第一行包含一个整数 $N$ $(2 \leq N \leq 10^5)$，表示顶点（以及松鼠）的数量。

接下来的 $N-1$ 行，每行包含两个空格分隔的整数 $u$ 和 $v$ $(1 \leq u, v \leq N, u \neq v)$，表示顶点 $u$ 和 $v$ 之间有一条边。任意一对顶点之间至多有一条边，且这些边构成一棵树。

输出格式

输出一行，包含 $N$ 个空格分隔的整数 $d_1, d_2, \ldots, d_N$，满足 $N \leq d_i \leq 2N-1$，其中 $d_i$ 是你希望分配给位于顶点 $i$ 的松鼠的橡果数量。如果经过全部 $N$ 次偷窃后，每只松鼠最终拥有的橡果数量与它最初拥有的数量相同，你的方案将被视为正确。可以证明，这样的橡果分配总是存在的。

5
1 2
1 3
1 4
2 5

6 5 7 7 9

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

14 15 10 9 13 14 14 14

提示

翻译由 DeepSeek V3.2 完成