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 very expensive but equally valued items.
To spice things up (and spend less), YAOGS however opts for an additional challenge, as follows. The available items are positioned along some, but possibly not all of the alleys of YAOGS's headquarters; each alley can thus contain , or more items. For reasons unknown, these alleys form a connected, undirected, acyclic graph (i.e., a tree) with nodes, numbered from to .
The winner knows 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 and an end node . She can then collect all the items on the (unique) path from to 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?
Input
Each line contains two integers. The fist line contains the numbers and . Then follow lines; the -th such line contains two integers and , meaning that there is an edge between the nodes and of the tree. The set of edges describes a valid tree structure.
Output
Prinr one integer: the maximum number of items that can be collected by the winner.
Examples
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 and . In the second one, the four items may be collected by choosing, for instance, nodes and .