E. Eliminate Tree
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree on $$$n$$$ 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 $$$(u, v)$$$ 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?

Input

The first line of input contains $$$n$$$ ($$$1\leq n\leq 2 \cdot 10^5$$$)  — the number of nodes of the tree.

The $$$i$$$-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

Output a single integer  — the smallest number of operations you need to perform to remove all the vertices from the tree.

Examples
Input
5
1 2
2 3
3 4
3 5
Output
4
Input
4
1 2
2 3
3 4
Output
2
Note

In the first sample, you can do the following sequence of operations:

  • Take edge $$$(1, 2)$$$, and remove vertices $$$1$$$ and $$$2$$$.
  • Add vertex $$$6$$$, connect it to vertex $$$5$$$.
  • Take edge $$$(4, 3)$$$, and remove vertices $$$4$$$ and $$$3$$$.
  • Take edge $$$(5, 6)$$$, and remove vertices $$$5$$$ and $$$6$$$.