Cow at Large (Platinum)

Cornered at last, Bessie has gone to ground in a remote farm. The farm has $N$ barns ($2 \leq N \leq 7 \times 10^4$) and $N-1$ bidirectional tunnels between barns, so there is exactly one path between every pair of barns. A barn with only one tunnel is an exit.

When morning comes, Bessie surfaces at some barn and tries to reach an exit. The moment she surfaces, the law pinpoints her location. Farmers then start at various exit barns and try to catch her. The farmers move at the same speed as Bessie, so in each time step each farmer can move from one barn to an adjacent barn, and so can Bessie. The farmers always know where Bessie is, and Bessie always knows where the farmers are. The farmers catch Bessie if at any instant a farmer is in the same barn as Bessie, or crossing the same tunnel as Bessie. Bessie escapes if she reaches an exit barn strictly before any farmer catches her.

Bessie has not decided where to surface. For each of the $N$ barns, find the minimum number of farmers needed to catch Bessie if she surfaced there, assuming the farmers distribute themselves optimally among the exit barns.

The first line contains $N$. Each of the next $N-1$ lines contains two integers between $1$ and $N$, describing a tunnel between those two barns.

Print $N$ lines. The $i$th line holds the minimum number of farmers needed to catch Bessie if she surfaced at barn $i$.