Fulkerson

Lester and Delbert already know how to disconnect a railroad network by exploding the minimum possible number of railways. That turned out to be pretty easy, so they went on to another interesting problem: how to rob the Federal Bank. Now they need your help preparing an escape plan.

The bank is located in a city with $N$ intersections and $N - 1$ bidirectional roads connecting them. All roads have the same length. It is possible to get from any intersection to any other using the road network.

To ensure a safe escape, Lester and Delbert plan to hire $K$ alert groups and place them at different intersections to collect information about police movements. Once the placement is fixed, for each intersection they compute the minimum number of roads one needs to travel to reach some alert group. The maximum of this value over all intersections is called the threat level of the placement.

Lester wants to hire only one alert group, while Delbert prefers to use $N$ of them. The solution will most likely lie somewhere in between, so calculate the minimum possible threat level for every value of $K$.

The first line of input contains a single integer $N$, the number of intersections in the city ($1 \leq N \leq 150\,000$). The next $N-1$ lines contain descriptions of the roads. Each description consists of two integers $u$ and $v$, denoting that there is a road between these intersections ($1 \le u, v \le N$, $u \neq v$). It is guaranteed that it is possible to get from any intersection to any other using the road network.

The output must consist of $N$ integers. The $i$-th of these integers must be equal to the minimal possible threat level that could be achieved by using exactly $i$ alert groups.