Cowntagion#10367
Farmer John and his fellow farmers are working tirelessly to contain the spread of the dangerous cattle disease COWVID-19 on their farms.
There are farms under observation, numbered from to . The farms are connected by n-1 roads, and it is possible to reach any farm from farm by following some sequence of roads.
Unfortunately, a cow on farm has just tested positive for COWVID-19. So far, no other cow — neither on this farm nor on any of the others — is infected. However, due to the extremely contagious nature of the disease, Farmer John realizes that on each subsequent day one of two events may occur:
a super-spreading event occurs on some farm, doubling the number of infected cows there;
one infected cow moves along a road from one farm to a neighboring one.
Farmer John is worried about how quickly the outbreak may spread. Help him determine the minimum possible number of days before every farm has at least one infected cow.
The first line contains one integer n~(1 \le n \le 10^5). Each of the following n - 1 lines contains two integers and , describing a road between farms and b~(1 \le a, b \le n).
Print the minimum number of days after which the outbreak may reach every farm.
One possible sequence of events corresponding to the example is the following:
first, the number of infected cows on farm doubles twice, so after days there are infected cows there. Then, over the next days, one infected cow moves from farm to farms , , and respectively. Thus, after days each farm has at least one infected cow.
Example 1