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 ≤ n ≤ 10⁵.

Output

Print the minimum cost to color each tree.