灵力之泉

题号：NC229813
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

传说中，天井下是一种藏在屋檐下的妖怪，她可以在屋檐之间传输灵力。

天井下常驻的屋檐共有 $n$ 个，依次标号为 $1, 2, \ldots, n$ 。屋檐之间有 $n-1$ 条双向小路连接，且从任意屋檐出发，天井下总能沿着小路移动到另一个屋檐下。

现在，天井下可以任选一个屋檐，在该屋檐下放置灵力之泉。时刻 $t = 0$ 时，只有拥有灵力之泉的屋檐充满灵力。每一个时刻 $t$ 时，若屋檐 $u$ 充满灵力，那么天井下可以任选至多 $w_u$ 个与屋檐 $u$ 有小路直接相连的屋檐，并让这些屋檐在 $t+1$ 时刻充满灵力。

天井下希望让每个屋檐都充满灵力，并且达成该条件的时刻越早越好，但是她还没有确定选择在哪个屋檐下放置灵力之泉。请你计算分别在屋檐 $1, 2, \ldots, n$ 下放置灵力之泉，达成条件的最早时刻是多少。

输入描述:

第一行为一个用空格分隔的整数  ()，表示屋檐的个数。

第二行为  个用空格分隔的整数 （）。

接下来的  行，每行两个整数  ()，表示屋檐  之间有一条双向小路连接。

保证屋檐的连接情况满足：从任意屋檐出发，天井下总能沿着小路移动到另一个屋檐下。

输出描述:

输出  行，每行输出一个整数，其中第  行的数表示在屋檐  下放置灵力之泉，达成条件的最早时刻。

示例1

输入

复制

输出

复制

说明

在屋檐  下放置灵力之泉时，各时刻拥有灵力的屋檐编号如下：

1. ：
2. ：
3. ：

在屋檐  下放置灵力之泉时，各时刻拥有灵力的屋檐编号如下：

1. ：
2. ：
3. ：
4. ：

在屋檐  下放置灵力之泉时，各时刻拥有灵力的屋檐编号如下：

1. ：
2. ：
3. ：

在屋檐  下放置灵力之泉时，各时刻拥有灵力的屋檐编号如下：

1. ：
2. ：
3. ：
4. ：

示例2

输入

复制

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

输出

复制