Subway

A certain city has been building its subway for a long time. Its finances were mismanaged and the costs so badly underestimated that no money was left to buy trains. As a result far too many stations were built and only some of the planned tunnels were finished, barely enough to keep every pair of stations connected. Each tunnel is bidirectional, and the number of tunnels is exactly one less than the number of stations. With the money that was left, only a handful of trains could be bought.

To save face, the board of directors asked you to plan the subway routes so that as many stations as possible are served. Each train runs on one specified route. A route cannot branch (no three tunnels meeting at a single station may belong to the same route). Different routes may share the same station or the same tunnel.

Write a program that:

• reads a description of the tunnel system and the number of subway lines to be planned from standard input,
• computes the maximum number of stations that can be covered by the given number of subway lines,
• writes the result to standard output.

The first line contains two integers $n$ and $l$ separated by a single space ($2 \le n \le 1{,}000{,}000$, $0 \le l \le n$). Here $n$ is the number of stations and $l$ is the number of subway lines to be planned. The stations are numbered from $1$ to $n$.

Each of the next $n-1$ lines contains two distinct integers separated by a single space. In line $i+1$, the integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n$) are the numbers of the two stations joined by the $i$-th tunnel.

Print a single integer: the maximum number of stations that can be covered by the train routes.

The figure shows the tunnel system (with the subway routes marked) in one of the optimal configurations.