Olympic goodies

Freshly arrived on the market, retailer YAOGS (Yet Another Olympic Goodies Seller) sells very expensive Olympics-themed items. To make themselves better known to the public, they halfheartedly decide to give away some of these items via a contest: the first person to answer correctly the question "How many circles are there in the Olympic Games logo?" can thus gain up to $p$ very expensive but equally valued items.

To spice things up (and spend less), YAOGS however opts for an additional challenge, as follows. The $p$ available items are positioned along some, but possibly not all of the alleys of YAOGS's headquarters; each alley can thus contain $0,1$, or more items. For reasons unknown, these alleys form a connected, undirected, acyclic graph (i.e., a tree) with $n$ nodes, numbered from $0$ to $n-1$.

The winner knows $n$ but has no idea about either the tree structure or the items' placement. Once goodies are placed, her task is to choose a start node $m$ and an end node $n$. She can then collect all the items on the (unique) path from $m$ to $n$ in the tree.

YAOGS decides to cleverly place the goodies so that they minimise the maximum number of items that can possibly be collected. Assuming they properly carry out this task, what is the maximum number of items the winner can collect?

Giriş verilənləri

Each line contains two integers. The fist line contains the numbers $n$ and $p(1\le n,p\le 10^5$. Then follow $n-1$ lines; the $k$-th such line contains two integers $a_k$ and $b_k(0\le a_k,b_k\le n-1)$, meaning that there is an edge between the nodes $a_k$ and $b_k$ of the tree. The set of edges describes a valid tree structure.

Çıxış verilənləri

Prinr one integer: the maximum number of items that can be collected by the winner.

Nümunələr

For the tree in the sample input, depicted below, an optimal item placement by YAOGS guarantees that the winner cannot collect more than four items.

The figures below show two possible item placements to achieve this optimality. In the first one, the four items may be collected by choosing, for instance, nodes $1$ and $3$. In the second one, the four items may be collected by choosing, for instance, nodes $0$ and $4$.