Cow at Large (Platinum)#10427
Cornered at last, Bessie has gone to ground on a remote farm. The farm consists of barns and n - 1 bidirectional tunnels between them, such that there is a unique path between every pair of barns. Every barn with only one tunnel is an exit. When morning comes, Bessie will surface at some barn and attempt to reach an exit.
However, the moment Bessie surfaces at a barn, the law will be able to pinpoint her location. Some farmers will then start from various exit barns and attempt to catch Bessie. The farmers move at the same speed as Bessie, so in each time step each farmer can move from one barn to an adjacent one. The farmers know where Bessie is at all times, and Bessie knows where the farmers are at all times. The farmers catch Bessie if at any moment a farmer is in the same barn as Bessie or is crossing the same tunnel as she is. Conversely, Bessie escapes if she reaches an exit barn strictly before any farmer catches her.
Bessie is unsure at which barn she should surface. For each of the barns, help her determine the minimum number of farmers needed to catch her if she surfaced there, assuming that the farmers position themselves optimally among the exit barns.
The first line contains an integer n~(2 \le n \le 7 \cdot 10^4). Each of the next n - 1 lines contains two integers a_i and b_i~(1 \le a_i, b_i \le n), describing a tunnel between barns a_i and b_i.
Print lines. The -th line must contain the minimum number of farmers needed to catch Bessie if she surfaces at barn .
Example 1