给定一棵有 $N$ 个顶点的树（顶点编号从 $1$ 到 $N$），其中 $1$ 为树的根。树上每条边的权重均为 $1$。

定义 $d(u, v)$ 为顶点 $u$ 和 $v$ 之间的距离。

定义 $c(w)=\sum \limits_{v \in T} d(w, v)$。如果树 $T$ 上的一个顶点 $w$ 满足 $c(w) \le \min \limits_{u \in T} c(u)$，则称 $w$ 为该树的关键点。

现在，对于所有 $i \in [1, N]$，你需要输出以顶点 $i$ 为根的子树中的所有“关键点”。

输入格式

输入的第一行包含一个整数 $N$，表示树的顶点数。

接下来 $N - 1$ 行，第 $i$ 行包含两个整数 $a_i, b_i$，表示树上的第 $i$ 条边。

• $1 \le N \le 2 \times 10^5$
• $1 \le a_i, b_i \le N$
• 输入保证是一棵树

输出格式

输出 $N$ 行。

在第 $i$ 行，按升序输出以顶点 $i$ 为根的子树中的“关键点”。若子树中有多个关键点，请用空格隔开。

样例

输入格式 1

4
1 2
2 3
2 4

输出格式 1

2
2
3
4