Cow at Large#10424
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, 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 before any farmer catches her.
Bessie is unsure of her chances of success, which depend on the number of farmers the law is able to deploy. Given that Bessie surfaces at barn , help her determine the minimum number of farmers needed to catch her, assuming that the farmers position themselves optimally among the exit barns.
The first line contains two integers and k~(2 \le n \le 10^5, 1 \le k \le n). 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 the minimum number of farmers needed to guarantee that Bessie is caught.
Example 1