有 $N$ 只松鼠在树上储存橡子。（植物学上的）橡树也是图论中的树：一个连通图，包含 $N$ 个顶点，编号从 $1$ 到 $N$，以及 $N-1$ 条无向边。每只松鼠坐在树的不同顶点上，如果两只松鼠所在的顶点共享一条边，则称它们为邻居。

按照顶点编号的升序，从位于顶点 $1$ 的松鼠开始，每只松鼠从其当前拥有橡子最多的邻居那里偷走一个橡子。如果多个邻居并列拥有最多的橡子，该松鼠会从每一个这样的邻居那里各偷走一个橡子！

为了限制这些闹剧的影响，你需要给松鼠分配橡子，使得每只松鼠开始时至少有 $N$ 个橡子（这样就不会因为被偷而耗尽橡子），并且在所有 $N$ 只松鼠完成相互偷窃后，它们拥有的橡子数量与最初相同。可以证明，存在一种分配方式，使得每只松鼠开始时最多有 $2N-1$ 个橡子。请找出满足这些条件的任意一种分配方案。

输入格式

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

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

输出格式

输出 $N$ 个空格分隔的整数 $d_1, d_2, \dots, d_N$，满足 $N \le d_i \le 2N-1$，其中 $d_i$ 是你希望分配给位于顶点 $i$ 的松鼠的橡子数量。如果每只松鼠在所有 $N$ 次偷窃发生后，最终拥有的橡子数量与开始时相同，则你的解将被接受。可以证明，这样的橡子分配方案总是存在的。

样例

样例输入 1

5
1 2
1 3
1 4
2 5

样例输出 1

6 5 7 7 9

样例输入 2

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

样例输出 2

14 15 10 9 13 14 14 14