Chain Transformation

Bob, an apprentice blacksmith, has constructed an unfinished chain by following a traditional procedure. Initially, he creates a ring. Then for every subsequent ring, he attaches it to an already existing ring in the chain. As a result, the final structure is a tree, where each ring represents a vertex and every attachment represents an edge.

However, a valid straight chain must form a simple path, in which every ring is connected to at most two other rings, and the entire chain is connected. To achieve this, Bob is allowed to perform the following operation:

• Select a ring A that is connected to some ring B in the chain.
• Detach A from B and then reconnect A to another ring C in the chain. (If A is connected to any other rings besides B, those connections remain intact throughout the operation.)

Mathematically, let \(d(v)\) denote the degree of vertex \(v\) in the tree. In a proper straight chain, we must have \(d(v) \le 2\) for every vertex, with exactly two vertices of degree 1 (the endpoints) and the rest with degree 2. In the given tree, vertices with \(d(v)>2\) have extra connections that need to be removed via the above operation. In each operation, by reattaching a ring, Bob effectively reduces the degree of one vertex (whichever served as the originally connected ring B) by 1. Hence, the minimum number of operations required is exactly the sum over all vertices of the extra degree beyond 2:

[ \text{Minimum Operations} = \sum_{v=1}^{n} \max(0, d(v)-2). ]

Your task is to compute this minimum number of operations.

inputFormat

The input begins with a single integer \(n\) (\(1 \le n \le 10^5\)), representing the number of rings. The following \(n-1\) lines each contain two integers \(u\) and \(v\) (\(1 \le u, v \le n\)), which describe an edge between rings \(u\) and \(v\). It is guaranteed that these edges form a tree.

outputFormat

Output a single integer, the minimum number of operations required to transform the unfinished chain into a straight chain.

sample

4
1 2
1 3
1 4

1