Defend Hogwarts

After Voldemort’s dark forces seized control of the Ministry of Magic and Hogwarts School of Witchcraft and Wizardry, Harry, Ron, and Hermione were forced into hiding. In order to fulfill Professor Dumbledore’s last wish of destroying Voldemort’s Horcruxes, Harry learned that if they could obtain the legendary Deathly Hallows, Voldemort would be doomed.

However, after regaining control of Hogwarts with the help of the Order of the Phoenix, the enraged Voldemort led his Death Eaters and other dark creatures in an all‐out assault on the castle. Professor McGonagall immediately evacuated the students and started defending Hogwarts.

Hogwarts has n main buildings numbered from 1 to n. These buildings are connected by magical roads forming a tree, i.e. there is exactly one simple path between any two buildings. Over the years, each building has acquired many protective spells such as the "Colossus Charm", "Enemy-Repelling Charm", and so on. A building can be protected by having a member of the Order visit it to cast the spell. Note that once a building’s protection has been activated, it remains active forever even if Voldemort’s forces later reconquer it.

At time 0, Voldemort’s army arrives at building 1 (the school gate) where the protection spell is already active. The army conquers any building it attacks in 1 hour. After conquering a building, the army immediately (without taking additional time) moves to one of its adjacent buildings; they may even choose a building that has been conquered before. Meanwhile, except for building 1, none of the other buildings have been protected yet. At time 0, the Order dispatches some members to other buildings to activate protective spells. Each member can instantly reach any building and start casting a spell that requires 1 hour to complete. Importantly, when the army conquers a building, the Order can, upon learning which adjacent building the enemy will attack next, immediately decide (in no time) to send members to cast spells in the required buildings. However, if a building’s protection is already active, it does not need any further attention.

The Order’s goal is to ensure that no matter how Voldemort’s army moves, every building that the army attacks will already have its protection activated at the time of the attack. In order to concentrate their strength on fighting Voldemort’s forces, the Order wishes to minimize the number of members that must be dispatched. Your task is to compute the least number of members required.

Note that if a spell is started at time t, it becomes effective at time t+1. At time 0 the members start activating spells in some buildings, and at time 1 these spells complete. Then, based on the enemy’s current move, additional members can be redeployed.

Observation: For any building v (other than 1), assume its distance from building 1 is d (thus the enemy will reach it at time d). To guarantee that v is protected by time d, a member has to start casting the spell no later than time d-1. In particular, at time 0, protective spells must be activated simultaneously in all neighbors of building 1. Similarly, if the enemy reaches a building v with degree deg(v) at some time, then at that moment protection must already be completed in all of its adjacent buildings except the one it came from (i.e. deg(v) - 1 buildings). Thus, the minimum number of members required is governed by the maximum number of simultaneous activations needed, that is:

$$\max\big(\deg(1), \; \max_{v\ge2}\{\deg(v)-1\}\big)$$

inputFormat

The first line contains an integer n (1 ≤ n ≤ 10⁵), representing the number of buildings. Each of the following n-1 lines contains two integers u and v (1 ≤ u, v ≤ n), denoting a magical road connecting building u and building v. It is guaranteed that the buildings form a tree.

outputFormat

Output a single integer — the minimum number of members that need to be dispatched by the Order of the Phoenix.

sample

1

0