#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline bool chkmin(T &a, const T &b) {
  return b < a ? a = b, 1 : 0;
}
template <typename T>
inline bool chkmax(T &a, const T &b) {
  return a < b ? a = b, 1 : 0;
}
const int oo = 0x3f3f3f3f;
const int maxn = 500100;
int n;
vector<int> adj[maxn + 5];
long long ans = 0;
int fa[maxn + 5];
int sz[maxn + 5];
int lk[maxn + 5];
int dfs_seq[maxn + 5];
int dfs_tot;
void dfs0(int first, int f = -1) {
  dfs_seq[dfs_tot++] = first;
  fa[first] = f;
  sz[first] = 1;
  for (auto second : adj[first])
    if (second != f) {
      dfs0(second, first);
      if (!~lk[second]) {
        if (!~lk[first]) {
          lk[lk[first] = second] = first;
        }
      }
      sz[first] += sz[second];
    }
}
bool visv[maxn + 5], visu[maxn + 5];
int upu[maxn + 5], downu[maxn + 5], upv[maxn + 5], downv[maxn + 5];
int up[maxn + 5], down[maxn + 5];
bool hasu[maxn + 5], hasv[maxn + 5];
void dfs1(int first, bool *vis) {
  if (vis[first]) return;
  vis[first] = 1;
  for (auto second : adj[first]) {
    assert(~lk[second]);
    dfs1(lk[second], vis);
  }
}
int main() {
  scanf("%d", &n);
  if (n & 1) {
    printf("0\n");
    return 0;
  }
  for (int i = (0), i_end_ = (n - 1); i < i_end_; ++i) {
    int u, v;
    scanf("%d%d", &u, &v), --u, --v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  memset(lk, -1, sizeof lk);
  dfs0(0);
  vector<int> no_match;
  for (int i = (0), i_end_ = (n); i < i_end_; ++i)
    if (!~lk[i]) no_match.push_back(i);
  if ((int((no_match).size())) == 0) {
    for (int i = n - 1; i >= 0; --i) {
      int first = dfs_seq[i];
      if (lk[first] == fa[first]) {
        down[first] = 1;
        for (auto second : adj[first])
          if (second != fa[first]) {
            down[first] += down[lk[second]];
          }
      }
    }
    for (int i = (0), i_end_ = (n); i < i_end_; ++i) {
      int first = dfs_seq[i];
      if (lk[first] != fa[first]) {
        int sum = 1;
        if (~fa[first]) {
          if (lk[fa[first]] == fa[fa[first]]) {
            sum += up[fa[first]];
          } else
            sum += down[lk[fa[first]]];
        }
        for (auto second : adj[first])
          if (second != fa[first] && second != lk[first]) {
            sum += down[lk[second]];
          }
        up[lk[first]] = sum;
      }
    }
    for (int i = (0), i_end_ = (n); i < i_end_; ++i)
      if (~fa[i]) {
        if (lk[i] == fa[i]) {
          ans += (long long)down[i] * up[i];
        } else
          ans += (long long)sz[i] * (n - sz[i]);
      }
    cout << ans << endl;
  } else if ((int((no_match).size())) == 2) {
    int u = no_match[0], v = no_match[1];
    int tmpu = u;
    while (~tmpu) {
      hasu[tmpu] = 1;
      tmpu = fa[tmpu];
    }
    int tmpv = v;
    while (~tmpv) {
      hasv[tmpv] = 1;
      tmpv = fa[tmpv];
    }
    dfs1(u, visu);
    dfs1(v, visv);
    for (int i = n - 1; i >= 0; --i) {
      int first = dfs_seq[i];
      down[first] = visu[first] ^ visv[first];
      downu[first] = visu[first];
      downv[first] = visv[first];
      for (auto second : adj[first])
        if (second != fa[first]) {
          down[first] += down[second];
          downu[first] += downu[second];
          downv[first] += downv[second];
        }
    }
    for (int i = (0), i_end_ = (n); i < i_end_; ++i) {
      up[i] = down[0] - down[i];
      upu[i] = downu[0] - downu[i];
      upv[i] = downv[0] - downv[i];
    }
    for (int i = (1), i_end_ = (n); i < i_end_; ++i) {
      if (lk[i] == fa[i]) {
        if (visu[fa[i]] && visv[fa[i]]) {
          ans += (long long)upu[i] * down[i];
        } else if (visu[fa[i]]) {
          ans += (long long)upu[i] * downv[i];
        } else if (visv[fa[i]]) {
          ans += (long long)upv[i] * downu[i];
        }
        if (visu[i] && visv[i]) {
          ans += (long long)downu[i] * up[i];
        } else if (visu[i]) {
          ans += (long long)downu[i] * upv[i];
        } else if (visv[i]) {
          ans += (long long)downv[i] * upu[i];
        }
      } else {
        if (hasu[i] && !hasv[i]) {
          ans += (long long)downu[i] * upv[i];
        } else if (hasv[i] && !hasu[i]) {
          ans += (long long)downv[i] * upu[i];
        }
      }
    }
    cout << ans << endl;
  } else {
    printf("0\n");
  }
  return 0;
}

### Prompt

Generate a CPP solution to the following problem:

Sloth is bad, mkay? So we decided to prepare a problem to punish lazy guys.

You are given a tree, you should count the number of ways to remove an edge from it and then add an edge to it such that the final graph is a tree and has a perfect matching. Two ways of this operation are considered different if their removed edges or their added edges aren't the same. The removed edge and the added edge can be equal.

A perfect matching is a subset of edges such that each vertex is an endpoint of exactly one of these edges.

Input

The first line contains n (2 ≤ n ≤ 5·105) — the number of vertices.

Each of the next n - 1 lines contains two integers a and b (1 ≤ a, b ≤ n) — the endpoints of one edge. It's guaranteed that the graph is a tree.

Output

Output a single integer — the answer to the problem.

Examples

Input

4
1 2
2 3
3 4


Output

8


Input

5
1 2
2 3
3 4
3 5


Output

0


Input

8
1 2
2 3
3 4
1 5
5 6
6 7
1 8


Output

22

Note

In first sample, there are 8 ways:

  * edge between 2 and 3 turns to edge between 1 and 3, 
  * edge between 2 and 3 turns to edge between 1 and 4, 
  * edge between 2 and 3 turns to edge between 2 and 3, 
  * edge between 2 and 3 turns to edge between 2 and 4, 
  * edge between 1 and 2 turns to edge between 1 and 2, 
  * edge between 1 and 2 turns to edge between 1 and 4, 
  * edge between 3 and 4 turns to edge between 1 and 4, 
  * edge between 3 and 4 turns to edge between 3 and 4. 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline bool chkmin(T &a, const T &b) {
  return b < a ? a = b, 1 : 0;
}
template <typename T>
inline bool chkmax(T &a, const T &b) {
  return a < b ? a = b, 1 : 0;
}
const int oo = 0x3f3f3f3f;
const int maxn = 500100;
int n;
vector<int> adj[maxn + 5];
long long ans = 0;
int fa[maxn + 5];
int sz[maxn + 5];
int lk[maxn + 5];
int dfs_seq[maxn + 5];
int dfs_tot;
void dfs0(int first, int f = -1) {
  dfs_seq[dfs_tot++] = first;
  fa[first] = f;
  sz[first] = 1;
  for (auto second : adj[first])
    if (second != f) {
      dfs0(second, first);
      if (!~lk[second]) {
        if (!~lk[first]) {
          lk[lk[first] = second] = first;
        }
      }
      sz[first] += sz[second];
    }
}
bool visv[maxn + 5], visu[maxn + 5];
int upu[maxn + 5], downu[maxn + 5], upv[maxn + 5], downv[maxn + 5];
int up[maxn + 5], down[maxn + 5];
bool hasu[maxn + 5], hasv[maxn + 5];
void dfs1(int first, bool *vis) {
  if (vis[first]) return;
  vis[first] = 1;
  for (auto second : adj[first]) {
    assert(~lk[second]);
    dfs1(lk[second], vis);
  }
}
int main() {
  scanf("%d", &n);
  if (n & 1) {
    printf("0\n");
    return 0;
  }
  for (int i = (0), i_end_ = (n - 1); i < i_end_; ++i) {
    int u, v;
    scanf("%d%d", &u, &v), --u, --v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  memset(lk, -1, sizeof lk);
  dfs0(0);
  vector<int> no_match;
  for (int i = (0), i_end_ = (n); i < i_end_; ++i)
    if (!~lk[i]) no_match.push_back(i);
  if ((int((no_match).size())) == 0) {
    for (int i = n - 1; i >= 0; --i) {
      int first = dfs_seq[i];
      if (lk[first] == fa[first]) {
        down[first] = 1;
        for (auto second : adj[first])
          if (second != fa[first]) {
            down[first] += down[lk[second]];
          }
      }
    }
    for (int i = (0), i_end_ = (n); i < i_end_; ++i) {
      int first = dfs_seq[i];
      if (lk[first] != fa[first]) {
        int sum = 1;
        if (~fa[first]) {
          if (lk[fa[first]] == fa[fa[first]]) {
            sum += up[fa[first]];
          } else
            sum += down[lk[fa[first]]];
        }
        for (auto second : adj[first])
          if (second != fa[first] && second != lk[first]) {
            sum += down[lk[second]];
          }
        up[lk[first]] = sum;
      }
    }
    for (int i = (0), i_end_ = (n); i < i_end_; ++i)
      if (~fa[i]) {
        if (lk[i] == fa[i]) {
          ans += (long long)down[i] * up[i];
        } else
          ans += (long long)sz[i] * (n - sz[i]);
      }
    cout << ans << endl;
  } else if ((int((no_match).size())) == 2) {
    int u = no_match[0], v = no_match[1];
    int tmpu = u;
    while (~tmpu) {
      hasu[tmpu] = 1;
      tmpu = fa[tmpu];
    }
    int tmpv = v;
    while (~tmpv) {
      hasv[tmpv] = 1;
      tmpv = fa[tmpv];
    }
    dfs1(u, visu);
    dfs1(v, visv);
    for (int i = n - 1; i >= 0; --i) {
      int first = dfs_seq[i];
      down[first] = visu[first] ^ visv[first];
      downu[first] = visu[first];
      downv[first] = visv[first];
      for (auto second : adj[first])
        if (second != fa[first]) {
          down[first] += down[second];
          downu[first] += downu[second];
          downv[first] += downv[second];
        }
    }
    for (int i = (0), i_end_ = (n); i < i_end_; ++i) {
      up[i] = down[0] - down[i];
      upu[i] = downu[0] - downu[i];
      upv[i] = downv[0] - downv[i];
    }
    for (int i = (1), i_end_ = (n); i < i_end_; ++i) {
      if (lk[i] == fa[i]) {
        if (visu[fa[i]] && visv[fa[i]]) {
          ans += (long long)upu[i] * down[i];
        } else if (visu[fa[i]]) {
          ans += (long long)upu[i] * downv[i];
        } else if (visv[fa[i]]) {
          ans += (long long)upv[i] * downu[i];
        }
        if (visu[i] && visv[i]) {
          ans += (long long)downu[i] * up[i];
        } else if (visu[i]) {
          ans += (long long)downu[i] * upv[i];
        } else if (visv[i]) {
          ans += (long long)downv[i] * upu[i];
        }
      } else {
        if (hasu[i] && !hasv[i]) {
          ans += (long long)downu[i] * upv[i];
        } else if (hasv[i] && !hasu[i]) {
          ans += (long long)downv[i] * upu[i];
        }
      }
    }
    cout << ans << endl;
  } else {
    printf("0\n");
  }
  return 0;
}

```