#2386. 「USACO 2018.01 Platinum」Cow at Large

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

题目译自 USACO 2018 January Contest, Platinum Problem 2. Cow at Large

贝茜被农民们逼进了一个偏僻的农场。农场可视为一棵有 N 个结点的树,结点分别编号为 1\ldots N 。每个叶子结点都是出入口。
开始时,每个出入口都可以放一个农民(也可以不放)。每个时刻,贝茜和农民都可以移动到相邻的一个结点。如果某一时刻农民与贝茜相遇了(在边上或点上均算),则贝茜将被抓住。抓捕过程中,农民们与贝茜均知道对方在哪个结点。
请问:对于结点 i\,(1\le i\le N) ,如果开始时贝茜在该结点,最少有多少农民,她才会被抓住。

输入格式

第一行包含 N 。 在接下来的 N-1 行中,每行有两个在 1\sim N 范围内的整数,表示一条边。

输出格式

输出 N 行,第 i 行表示如果开始时贝茜在结点 i ,最少有多少农民,她才会被抓住。

样例

样例输入

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

样例输出

3
1
3
3
3
1
1

数据范围与提示

2≤N≤7\times 10^4