Optimal blue-red tree P24951

You are given an undirected connected graph with no cycles. You must paint every node either blue or red. Painting in blue costs 1 per node, while painting in red costs 2 per node. Your goal is to minimize the total cost of painting the tree. There is just one restriction: Each node can have, at most, one adjacent node with the same color than itself.

Input

Input consists of several trees, each one with the number of nodes $n$, followed by $n - 1$ pairs $x$ $y$ for the edges. Nodes are numbered from 0. Assume $1 \le n \le 10^5$.

Output

Print the minimum cost to color each tree.