Bessie 终于被逼到了绝境，躲进了一个偏远的农场。农场由 $N$ 个牛棚（$2 \leq N \leq 7 \cdot 10^4$）和 $N-1$ 条连接牛棚的双向隧道组成，使得任意两个牛棚之间都有唯一的路径。每个只有一个隧道连接的牛棚都是一个出口。当早晨到来时，Bessie 会在某个牛棚现身并试图到达一个出口。

但就在 Bessie 在某个牛棚现身的瞬间，执法人员就能确定她的位置。随后，一些农夫会从各个出口牛棚出发，试图抓住 Bessie。农夫的移动速度与 Bessie 相同（因此在每个时间步长内，每个农夫都可以从一个牛棚移动到相邻的牛棚）。农夫始终知道 Bessie 的位置，Bessie 也始终知道农夫的位置。如果任何时刻农夫与 Bessie 处于同一个牛棚，或者穿过同一条隧道，农夫就会抓住 Bessie。反之，如果 Bessie 在任何农夫抓住她之前严格先到达一个出口牛棚，她就成功逃脱了。

Bessie 不确定她应该在哪个牛棚现身。对于 $N$ 个牛棚中的每一个，请帮助 Bessie 确定：如果她从该牛棚现身，假设农夫在出口牛棚之间进行最优分配，那么抓住 Bessie 所需的最少农夫数量是多少。

注意，本题的时间限制略长于默认值：C/C++/Pascal 为 4 秒，Java/Python 为 8 秒。

输入格式

第一行包含 $N$。接下来的 $N-1$ 行，每行包含两个整数（范围在 $1 \ldots N$ 之间），描述两个牛棚之间的一条隧道。

输出格式

请输出 $N$ 行，其中第 $i$ 行输出表示如果 Bessie 在第 $i$ 个牛棚现身，抓住她所需的最少农夫数量。

样例

输入 1

7
1 2
1 3
3 4
3 5
4 6
5 7

输出 1

3
1
3
3
3
1
1