Migrated from Lutece 3115 birth of a new witch

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tag：点分树、LCA

贝阿朵莉切将右代宫战人招待进了黄金乡，他们将在这个全新的“棋盘”上展开“红与蓝的争锋”。

黄金乡由 $n$ 个编号为 $1\sim n$ 的场所构成，有 $n-1$ 条等长的道路将所有的场所连通在一起，换句话说，这 $n$ 个点构成了一棵树。

在每个场所的地下金库中，都藏有数不尽的黄金，贝阿朵莉切告诉战人，每个场所的黄金数量和其编号大小正相关，即编号为 $1$ 的场所拥有最少的黄金，编号为 $n$ 的场所拥有最多的黄金。

现在贝阿朵莉切要让战人快速回答她的问题：对于每个场所 $i\in [1,n-1]$ ，找到与场所 $i$ 树上距离最近，且黄金数量多于 $i$ 的场所 $j$ 。

如果合法的 $j$ 有多个（即存在多个编号大于 $i$ 的点 $j$ 满足它们到 $i$ 的距离最近且相等），回答她编号最小的那个。

Input

输入的第一行包括一个正整数 $n$ ，表示黄金乡包含的场所总数。

接下来的 $n-1$ 行每行包括两个整数 $u,v$ ，表示存在一条连接场所 $u$ 与场所 $v$ 的道路。

输入保证给出的道路信息构成一棵树。

Output

输出一行共包括 $n-1$ 个数，分别表示对于场所 $1,2,\cdots,n-1$ 的问题的答案。

Samples

6
1 6
2 5
4 5
3 5
5 6

6 5 5 5 6

5
5 1
1 3
3 2
2 4

3 3 4 5

Constraints

$2\le n\le 2\times 10^5,1\le u,v\le n,u\ne v$

Resources

2024 UESTC ICPC Training for Data Structures