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.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
int n;
int cnt[2];
vector<int> Adj[MAXN];
void DFS(int node, int p, int c) {
  cnt[c]++;
  for (auto x : Adj[node]) {
    if (x == p) {
      continue;
    }
    DFS(x, node, 1 - c);
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for (int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    Adj[u].push_back(v);
    Adj[v].push_back(u);
  }
  DFS(1, -1, 0);
  cout << min(cnt[0], cnt[1]) - 1;
}
