Migrated from Lutece 2725 我来抓人了

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

上路只会带线。 敌方上单总是一直带线，让 xx 非常难受。 但是峡谷地形四通八达，即使抓人也不一定抓得到。 具体的，峡谷地形可以看成一个 $n$ 个节点的树，所有英雄每秒都只能从一个节点移动到相邻节点上。 每个叶子结点都是进出点，即上单如果在叶子结点上，下一秒可以逃脱；初始时候所有叶子结点都可以布置一个己方英雄（也可以不放）。 由于布置了眼位，任意时刻 xx 队的英雄和敌方上单都知道对方的位置和树的结构。 现在 xx 想知道，对于树上每个节点 $i$ ，如果初始时候敌方上单在点 $i$，最小需要布置多少英雄才能抓到他。当敌方上单和 xx 队英雄相遇（点上和边上都算）就算抓到了。 当然英雄数量不止 $5$ 个

Input

第一行输入一个整数 $n\ (1\le n\le 10^5)$。 接下来 $n-1$ 行每行两个空格隔开的整数 $x,y$，表示有一条边连接$x,y$。 保证连接出来的是一棵树。

Output

输出 $n$ 行整数。 第 $i$ 行输出的整数表示如果敌方上单在点 $i$ 需要布置多少英雄才能抓到他。

Samples

9
1 2
1 3
3 4
4 5
4 6
2 7
7 8
8 9

2
2
2
3
1
1
2
2
1

Resources

2022 UESTC ICPC Training for Data Structures