P9608 [CERC2019] Bob in Wonderland

**This problem is translated from [CERC 2019](https://contest.felk.cvut.cz/19cerc/solved.html) “[Bob in Wonderland](https://contest.felk.cvut.cz/19cerc/solved/bob.pdf)”.**

As everyone knows, a chain consists of connected rings. Usually, all rings have the same shape and size. Bob is a blacksmith apprentice, and he is making his first iridium chain. He follows the traditional rules of chain making, which say: - If there is no chain, make a ring, and it becomes part of your chain. - If there is a chain, make a ring and connect it to another ring in the chain you already have. Bob made the first ring. Then, each time he made another ring, he connected it to some other ring in the chain, just as the rules told him. When he finished, he realized that what he created did not look like a normal chain at all. To straighten the chain, he repeatedly picked up two rings that could be the ends of the chain and tried to pull them as far apart as possible. But in different places, more “chains” were hanging down from the straightened part. Obviously, Bob’s work is not finished, and he decided to call the object he made an unfinished chain. After more thought, Bob came to the conclusion that he must more carefully disconnect some rings and reconnect them to the rest of the unfinished chain, in order to obtain the straight chain he wants to make. In a straight chain, each ring is connected to at most two other rings, and the straight chain cannot be separated into more parts without breaking a ring. Bob will now be more careful and will make progress using simple steps. In one step, on the unfinished chain, he chooses a ring A that is connected to ring B. Then, he separates A from B and reconnects A to another ring C in the unfinished chain. Except for ring B, throughout the step, Bob keeps all other rings that were originally connected to ring A still connected to ring A. What is the minimum number of steps needed for Bob to obtain a straight chain?

The first line contains an integer $N\ (1\le N\le 3\times 10^5)$, representing the number of rings in the unfinished chain. All rings are numbered $1, 2, \dots, N$. The next $N-1$ lines each contain two integers, representing the indices of two connected rings in the unfinished chain, given in any order. The unfinished chain is guaranteed to have only one connected component (that is, for any two rings, there exists a path connecting them).

Output one integer, representing the minimum number of steps to transform Bob’s unfinished chain into a straight chain.

### Sample Explanation  Translated by ChatGPT 5