Description

Farmer John and his team of farmers have been working day and night to control the spread of the cow infectious disease COWVID-19 among their farms.

They are monitoring a total of $N$ farms ($1 \le N \le 10^5$), numbered $1 \ldots N$. The farms are connected by $N - 1$ roads, such that every farm can be reached from farm $1$ by traveling along some roads.

Unfortunately, a cow on farm $1$ has tested positive for COWVID-19. For now, the other cows on this farm, as well as all cows on all other farms, are not infected yet. However, based on the fact that this disease spreads through contact, Farmer John predicts that each day, one of the following unfortunate events will happen:

(1) Within a farm, a “super spreader” causes the number of cows infected with COWVID-19 on that farm to double; or

(2) One cow infected with COWVID-19 travels from one farm to an adjacent farm along a road.

Farmer John is worried that the outbreak will quickly get out of control. Please help Farmer John compute the minimum number of days required until every farm has at least one infected cow.

Input Format

The first line of input contains an integer $N$. The next $N - 1$ lines each contain two space-separated integers $a$ and $b$, indicating a road between farms $a$ and $b$. Both $a$ and $b$ are in the range $1 \ldots N$.

Output Format

Output the minimum number of days required for the outbreak to reach all farms.

4
1 2
1 3
1 4

5

Hint

One possible sequence of events for the sample is as follows. The number of infected cows on farm $1$ doubles and then doubles again, so after $2$ days there are $4$ infected cows on farm $1$. Over the next $3$ days, one infected cow travels from farm $1$ to farms $2$, $3$, and $4$, respectively. After $5$ days, every farm has at least $1$ infected cow.

• In testdata 1–4, every farm (except farm $1$) is directly connected to farm $1$.
• In testdata 5–7, each of farms $2 \ldots N$ is connected to at most two roads.
• In testdata 8–15, there are no additional constraints.

Problem provided by: Dhruv Rohatgi.

Translated by ChatGPT 5