Farm Chase

Bessie has taken refuge on a remote farm that consists of (N) barns ((2 \leq N \leq 7 \cdot 10^4)) connected by (N-1) bidirectional tunnels so that there is a unique path between any pair of barns. A barn with only one tunnel is called an exit. When morning comes, Bessie may surface at some barn (v) and try to escape to an exit. However, as soon as she surfaces, farmers will start from chosen exit barns and move towards her at the same speed (one tunnel per time step). The farmers catch Bessie if at any time a farmer is in the same barn as her or if they cross the same tunnel in opposite directions at the same time. Bessie escapes if she manages to reach an exit strictly before any farmer catches her.

For a given barn (v) where Bessie might surface, the only way to catch her is to have a farmer start at the very exit she is headed for. This is because the unique path from (v) to any exit (w) is disjoint (except at (v)) from the path of any farmer starting at a different exit. Thus, if (v) is an exit (i.e. its degree is 1) then to catch Bessie a farmer must already be there, and the minimum number needed is 1. Otherwise, if (v) is not an exit, Bessie has the option to run to any exit. To guarantee her capture, the farmers must station themselves at every exit. In other words, the answer for a non‐exit barn is the total number of exits in the tree.

Your task is to calculate, for each barn (v), the minimum number of farmers that are needed to catch Bessie if she surfaces at barn (v), assuming that the farmers distribute themselves optimally among the exits.

Note: The time limits for this problem are slightly relaxed: 4 seconds for C/C++/Pascal and 8 seconds for Java/Python.

inputFormat

The first line contains a single integer (N) denoting the number of barns. The following (N-1) lines each contain two integers (u) and (v), indicating there is a bidirectional tunnel connecting barn (u) and barn (v). It is guaranteed that the barns form a tree.

outputFormat

Output (N) space‐separated integers. The (i)th integer represents the minimum number of farmers required to catch Bessie if she surfaces at barn (i).

sample

3
1 2
2 3

1 2 1