Toggle Tree Ornaments

For the New Year celebration, Bessie and her friends have built a giant tree decorated with glowing ornaments. Bessie can toggle (switch on/off) each ornament individually. Initially all ornaments are off. She wants to perform a sequence of toggles so that:

• At some moment, for every vertex r (with 1 ≤ r ≤ N), the set of currently turned‐on ornaments is exactly the subtree rooted at r. Here the subtree rooted at a vertex r is defined as the set of vertices v for which the unique path from the root (vertex 1) to v contains r. In formulas, if the tree has N vertices then $$T(r)=\{v\;:\; r \in \text{path}(1,v)\}.$$
• The process starts with all ornaments off and ends with all ornaments off.
• The total number of toggle operations (each switching one vertex) is minimized.

You are given a tree with vertices labeled 1,2,…,N (2 ≤ N ≤ 2·10⁵) rooted at 1. In one operation you can toggle a single vertex’s state (off ↔ on). Compute the minimum possible length of a sequence of operations satisfying the above conditions.

Note: When writing formulas, use LaTeX format. For example, the subtree of a vertex r is given by $$T(r)=\{v\;:\; r\in \text{path}(1,v)\}.$$

inputFormat

The first line contains a single integer N, the number of vertices in the tree.

Each of the following N−1 lines contains two integers u and v (1 ≤ u, v ≤ N) indicating that there is an edge between vertices u and v. The tree is rooted at vertex 1.

outputFormat

Output a single integer – the minimum number of toggles needed so that for every subtree of the tree (as defined above) there exists a moment when exactly the ornaments in that subtree are on, and the process starts and ends with all ornaments off.

sample

2
1 2

4