1375_G. Tree Modification
You are given a tree with n vertices. You are allowed to modify the structure of the tree through the following multi-step operation:

  1. Choose three vertices a, b, and c such that b is adjacent to both a and c. 
  2. For every vertex d other than b that is adjacent to a, remove the edge connecting d and a and add the edge connecting d and c. 
  3. Delete the edge connecting a and b and add the edge connecting a and c. 



As an example, consider the following tree:

<image>

The following diagram illustrates the sequence of steps that happen when we apply an operation to vertices 2, 4, and 5:

<image>

It can be proven that after each operation, the resulting graph is still a tree.

Find the minimum number of operations that must be performed to transform the tree into a star. A star is a tree with one vertex of degree n - 1, called its center, and n - 1 vertices of degree 1.

Input

The first line contains an integer n (3 ≤ n ≤ 2 ⋅ 10^5) — the number of vertices in the tree.

The i-th of the following n - 1 lines contains two integers u_i and v_i (1 ≤ u_i, v_i ≤ n, u_i ≠ v_i) denoting that there exists an edge connecting vertices u_i and v_i. It is guaranteed that the given edges form a tree.

Output

Print a single integer — the minimum number of operations needed to transform the tree into a star.

It can be proven that under the given constraints, it is always possible to transform the tree into a star using at most 10^{18} operations.

Examples

Input


6
4 5
2 6
3 2
1 2
2 4


Output


1


Input


4
2 4
4 1
3 4


Output


0

Note

The first test case corresponds to the tree shown in the statement. As we have seen before, we can transform the tree into a star with center at vertex 5 by applying a single operation to vertices 2, 4, and 5.

In the second test case, the given tree is already a star with the center at vertex 4, so no operations have to be performed.
```python
import sys
input = sys.stdin.readline
n=int(input())
graph=[[] for _ in range(n)]
for j in range(n-1):
    x,y=map(int,input().split())
    x-=1
    y-=1
    graph[x].append(y)
    graph[y].append(x)

color=[-1]*n
tem=[0]
visit=[0]*n
color[0]=0

while(tem!=[]):
    x=tem.pop()
    for i in graph[x]:
        if(color[i]==-1):
            visit[i]=1
            color[i]=1-color[x]
            tem.append(i)
k=color.count(1)  

print(min(k,n-k)-1)           

```