You are given a tree on nodes. You can perform the following operations:
Add a new vertex to the tree and connect it to exactly one already existing node
Take an edge with \text{deg}(u)=1 and \text{deg}(v)\leq2 and remove both of these vertices, as well as all edges connected to them, from the tree
What is the smallest number of operations you need to perform to remove all the vertices from the tree?
The first line of input contains (1\leq n\leq 2 \cdot 10^5) — the number of nodes of the tree.
The -th of the next n-1 lines contains two integers u_i and v_i (1 \leq u_i, v_i \leq n, u_i \neq v_i), denoting an edge between nodes u_i, v_i. It is guaranteed that these edges form a tree.
Output a single integer — the smallest number of operations you need to perform to remove all the vertices from the tree.
Example
Example 1
In the first sample, you can do the following sequence of operations:
Take edge , and remove vertices and .
Add vertex , connect it to vertex .
Take edge , and remove vertices and .
Take edge , and remove vertices and .