4165. 一无所有

【题目背景】

一无所有逃离了收容，在进化之前，他会伪装成一名普通员工出现在部门中，在其造成大规模伤亡前需要尽快镇压。

【题目描述】

脑叶公司的支部有 n 个部门，可以看作一个 n 个点的树，边为无向边，只有一条出边的部门称为 "出口"，发现一无所有后，主管可以任意在 "出口" 部门呼叫兔子增援协助镇压，每个出口只能呼叫一只兔子队，兔子队会瞬间到达“出口” 部门。

每一秒，兔子和一无所有都可以停留在原地或者移动到一个相邻部门。

一无所有会想方设法到达 “出口”部门。在其到达前，如果与兔子处于同一个部门或同一条边上，兔子就可以对一无所有进行镇压。

为了减小损伤，你需要知道如果一无所有出现在部门 x，至少需要在多少“出口”部门呼叫兔子才能使得一无所有无法在被镇压前到达“出口”。

对于所有的 x 求出答案。

【输入格式】

第一行一个整数 n 表示 n 个部门

接下来 n - 1 行每行两个整数 x y 表示 x 和 y 有连边。

【输出格式】

一共输出 n 行。

第 i 行表示当一无所有出现在第 i 个部门时的答案。

【样例输入】

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

【样例输出】

3
1
3
3
3
1
1

【数据规模与约定】

对于 40% 的数据 n <= 5000

对于 100% 的数据 n <= 100000

大样例

【来源】

USACO（洛谷链接）