Multi Ending Story

You are a programmer who loves bishojo games, a sub-genre of dating simulation games. A game titled 'I * C * P * C!' was released yesterday and has just arrived. The game has multiple endings. When you complete all of them, you get a special figure of the main heroine, Sakuya. You want to hurry and play, but first, think about how to complete all the endings in the shortest time.

Every branching point in this game is a choice between 'Yes' and 'No'. Once you take a different choice, the branched stories flow to different endings and never converge again, forming a binary tree. It takes exactly one minute to proceed from a branching point to another branching point or to an ending. Returning to the beginning of the game ('reset') and playing from the beginning to the first branching point take negligible time.

The game has a 'Quick Save' feature that can significantly reduce the time needed to complete it. It records the point where you are currently playing, and you can return to that point at any later time. You can record any number of times, but you can hold only the last recorded point. When you use Quick Save, it overwrites the previous record. If you want to return to an overwritten point, you must play from the beginning again.

Compute the shortest time needed to complete all the endings.

The first line contains one integer $N$ ($2 \leq N \leq 500{,}000$), the number of endings. The next $N-1$ lines describe the branching points. The $i$-th line describes the branching point with ID $i$ and contains two integers $Yes_i$ and $No_i$, the IDs of the next branching points when you select Yes or No. $Yes_i = N$ means that selecting Yes reaches an ending, and the same holds for $No_i = N$. The branching point with ID 1 is the first one. For every $i$, $i + 1 \leq Yes_i, No_i \leq N$ holds. Each branching point ID from 2 to $N-1$ appears exactly once among all the $Yes_i$ and $No_i$ values.

Print the shortest time in a line.