题目描述

给定一棵有 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。顶点 $u,v$ 之间的距离定义为连接它们的唯一简单路径上的边数。

对于每个顶点 $v=1,2,\ldots,N$，请在所有顶点中找出与 $v$ 距离最远的顶点并输出其编号。如果有多个顶点满足条件，输出其中编号最大的顶点。

输入格式

第一行输入正整数 $N$。接下来 $N-1$ 行，每行输入两个整数 $A_i,B_i$，表示树中的一条边。

输出格式

输出 $N$ 行，第 $i$ 行输出顶点 $i$ 对应的答案。

输入输出样例 #1

输入 #1

2
1 2

输出 #1

2
1

输入输出样例 #2

输入 #2

3
1 2
2 3

输出 #2

3
3
1

输入输出样例 #3

输入 #3

4
1 2
1 3
2 4

输出 #3

4
3
4
3

数据范围与约定

$2\le N\le5\times10^5$，$1\le A_i<B_i\le N$，输入保证构成一棵树。