Eliminate Tree#12937

Eliminate Tree

1 second
256 megabytes
Hard

You are given a tree on nodes. You can perform the following operations:

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 (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

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

Examples

Example

Loading
Loading

Example 1

Loading
Loading

Note

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 .