题目描述

圆滑博士经过多年打拼，已经变成了著名组织OLD SIX的教父。

OLD SIX的组织架构是一棵树，圆滑教父作为树根编号为 $1$ 。每个人在树状结构的深度 $k$ 作为他的级别（树根的深度为1），深度越小，级别越高，而一个人在树上的祖先为这个人的上司。

现在组织出现了"偷学者"，于是圆滑教父决定级别为 $k(k \geq 2)$ 的人最高只能认识级别为 $\lfloor \frac{k}{2} \rfloor$ 的上司（即深度小于$\lfloor \frac{k}{2} \rfloor$ 的上司无权结识），以防止他们泄漏太多秘密。特别的，圆滑教父能结识的最高级别即自己。

现在圆滑教父正在LMCI法庭和法官谈笑风声，你需要帮助他计算每个人能认识的级别最高的（深度最小的）上司的编号。

输入格式

第一行一个正整数 $n(1\leq n \leq 3\times10^5)$ ,表示树状结构的节点个数。

紧接着 $n - 1$行，每行两个正整数 $x, y (1 \leq x, y \leq n)$，表示树上的相邻的两个点。

树的根节点为 $1$ 号点。

输出格式

输出为一行 $n$ 个正整数，$k_1, k_2, \cdots, k_n$，其中 $k_i$ 表示 $i$ 号节点的能认识的级别最高的（深度最小的）上司的编号。

样例

6
1 2
2 3
3 4
1 5
4 6

1 1 1 2 1 2

数据范围

对于 $50\%$ 的数据满足 $n \leq 1000$。

对于 $100\%$ 的数据满足输入格式中的约束。