题目描述

给定一棵有 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。第 $i$ 条边连接顶点 $A_i$ 和 $B_i$。 定义两个顶点 $u$ 和 $v$ 之间的距离为以 $u$、$v$ 为端点的唯一路径上的边数。

对于每个顶点 $v=1,2,\dots,N$，请在顶点集合 ${1,2,\dots,N}$ 中找出与 $v$ 的距离最大的顶点编号。如果存在多个顶点的距离都相等且为最大值，则输出编号最大的那个顶点。

输入格式

输入共 $N$ 行：

• 第 $1$ 行包含一个整数 $N$，表示顶点个数。
• 接下来 $N-1$ 行，每行包含两个整数 $A_i\ B_i$，表示一条无向边连接顶点 $A_i$ 与 $B_i$。（$1\le i\le N-1$）

保证输入给出的是一棵树（连通且无环）。

输出格式

• 输出共 $N$ 行。

• 第 $i$ 行为顶点 $i$ 的答案：

• • 在顶点集合 ${1,\dots,N}$ 中与顶点 $i$ 距离最大的顶点的编号（若有多个，输出编号最大的那一个）。

样例输入 1

3
1 2
2 3

样例输出 1

3
3
1

样例输入 2

5
1 2
2 3
2 4
1 5

样例输出 2

4
5
5
5
4

说明

样例 $1$ 解释

• 与顶点 $1$ 距离最远的是顶点 $3$。
• 与顶点 $2$ 距离最远的顶点有 $1$ 和 $3$，取编号较大的 $3$。
• 与顶点 $3$ 距离最远的是顶点 $1$。

数据范围

• $2 \le N \le 5\times 10^{5}$；
• $1 \le A_i < B_i \le N$；
• 输入保证描述的是一棵树；
• 所有输入值均为整数。