Problem Description

After Voldemort’s dark forces took control of the Ministry of Magic and Hogwarts School of Witchcraft and Wizardry, Harry, Ron, and Hermione had to live in hiding. To fulfill Headmaster Dumbledore’s last wish, Harry had been secretly looking for chances to destroy Voldemort’s Horcruxes. By accident, he learned that if they could obtain the legendary three Deathly Hallows, Voldemort would surely die.

With the help of members of the Order of the Phoenix, Harry and his friends regained control of Hogwarts. This angered Voldemort, and he soon led a large number of Death Eaters and dark creatures to march on Hogwarts. Professor McGonagall urgently evacuated the students and began the battle to defend Hogwarts.

Hogwarts has $n$ main buildings, numbered from $1$ to $n$. The buildings are connected by magical roads and form a tree: between any two buildings, there is one and only one path (a path may consist of one or more roads). After many years, each building has many protective spells of its own, such as “Stone Base Triggering Charm”, “Anti-Enemy Trap Charm”, and “Protego Totalum”, etc. As long as someone goes there and casts the spell, the building can be protected.

Now, Voldemort’s army has arrived at building $1$ (the school gate). Members of the Order of the Phoenix are fighting at the gate and have already activated the gate’s protective magic. However, Voldemort’s army is too strong. The protective magic can only delay their attack. They can still capture one building per hour, and then the whole army randomly moves to another adjacent building (the movement takes no time; they may also go to a building that has already been captured).

At present, except for building $1$, the protective magic of all other buildings has not been activated yet. The Order of the Phoenix decides to send some members to other buildings to cast spells and activate their protective magic. Each member can instantly reach any building, and needs one hour to finish activating that building’s protection, after which they can go to other buildings. Their task is to ensure that no matter how Voldemort’s army moves, whenever the army arrives at a building, that building’s protective magic has already been activated. To concentrate more forces to directly fight Voldemort’s army, the Order of the Phoenix wants to send as few spell-casting members as possible.

Please compute the minimum number of members that must be sent.

Notes:

• At the same time Voldemort’s army arrives at building $1$ and starts attacking, the Order of the Phoenix sends members to cast spells in other buildings.

• After the army captures a building, the Order of the Phoenix members may decide which buildings to cast spells on, knowing which building the army will go to in the next hour. This decision process also takes no time.

• A building whose protective magic has been activated does not need to be cast again. Even if the army captures the building and later returns to it, the army will still attack for one hour in that building before leaving.

Input Format

The first line contains an integer $n$, the number of buildings.

The next $n-1$ lines each contain two integers $u, v$, indicating that there is a magical road between building $u$ and building $v$.

Output Format

Output one integer on a single line, the minimum number of spell-casting members needed.

7
1 2
1 3
2 5
2 6
7 2
4 1

3

Hint

Constraints

For $100\%$ of the testdata, $1 \le n \le 3 \times 10^5$.

Translated by ChatGPT 5