Problem F
Chopping Trees

After many years of research, Lolle has finally disproved Lalexander’s conjecture (which stated that $(a+b)^2=a^2+b^2$). Now feeling done with his mathematical career, Lolle retreats to the forest. Once a week, he goes out to chop down trees for timber. Lolle chose to move to a very particular forest: in this forest, all trees consist of $N$ nodes numbered from $1$ to $N$, connected by $N-1$ branches. Of course, the trees are held together by the branches, meaning that all pairs of nodes are indirectly connected by one or more branches. Although all trees have the same number of nodes, they can be connected in different ways, which always makes it a challenge to chop them down efficiently.

Lolle now wants to bring home a particular tree. Each node has bark on it. To be able to use the tree, he needs to peel off the bark from each node and remove all branches. To peel nodes and remove branches, he can perform a chop. To perform a chop, he chooses two nodes $a$ and $b$ that are not necessarily adjacent. For each node between $a$ and $b$ (including $a$ and $b$), he peels the node and then chops off all the branches attached to the node. When the branches are chopped off, the tree will be divided into smaller connected trees. He can then perform chops in these smaller trees. Note that he can only choose two endpoints for a chop if they are connected by a path of one or more branches.

Since Lolle isn’t keen on doing math anymore, he wants help finding the minimum number of chops needed to peel all nodes and remove all branches.

Input

The first line contains the integer $N$ ($1 \leq N \leq 10^5$), the number of nodes the tree consists of.

The following $N-1$ lines each contain the integers $a$ and $b$ ($1 \leq a,b \leq N$). This means that there is a branch between the nodes numbered $a$ and $b$. It is guaranteed that each node is indirectly connected to all other nodes through one or more branches.

Output

Print an integer: the minimum number of chops that Lolle needs to peel all nodes and remove all branches.

Points

Your solution will be tested on several test case groups. To get the points for a group, it must pass all the test cases in the group.

Explanation of sample 1:

At the beginning, the tree looks like this.

If Lolle makes a chop where $a=1$ and $b=4$ are the light red nodes, all the nodes marked in red will be chopped off, as the edges between $1-2$, $2-3$, and $3-4$ will be cut.

The remaining nodes that haven’t been chopped off are as follows:

He can then chop along the nodes $a=6$ and $b=7$, so that the edge between $6-5$ and $5-7$ is cut.

Explanation of sample 2:

Even if there aren’t any branches, the bark on node number $1$ must be peeled off. To do this, Lolle can perform a chop with $a=b=1$.

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

2

1

1