#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
const int UNDEF = -1;
const int INF = 1 << 30;
template <typename T>
inline bool chkmax(T &aa, T bb) {
  return aa < bb ? aa = bb, true : false;
}
template <typename T>
inline bool chkmin(T &aa, T bb) {
  return aa > bb ? aa = bb, true : false;
}
int rint();
char rch();
long long rlong();
const int mn = 5e5 + 2;
vector<int> g[mn];
class EulerEdge {
  static const int maxn = mn;
  int w[maxn];
  typedef struct S {
    int sum = 0;
    S() { sum = 0; }
    S(const int &x) { sum = x; }
    S operator*(const S &b) const { return S(sum + b.sum); }
    void upd(int x) { sum++; }
  } S;
  S identity = S(0);
  typedef struct VS {
    vector<S> prefix;
    vector<S> suffix;
  } VS;
  S t[maxn];
  VS vt[maxn];

 public:
  void euler_init(int x, int p) {
    int numchildren = g[x].size() - ((p == -1) ? 0 : 1);
    for (auto &y : g[x]) {
      if (y == p) continue;
      euler_init(y, x);
      t[x] = t[x] * t[y];
    }
    t[x].upd(x);
    {
      S prefix = identity;
      vt[x].prefix.resize(numchildren);
      int id = 0;
      for (auto &y : g[x]) {
        if (y == p) continue;
        vt[x].prefix[id] = prefix;
        prefix = prefix * t[y];
        id++;
      }
    }
    {
      S suffix = identity;
      vt[x].suffix.resize(numchildren);
      int id = 0;
      for (auto it = g[x].rbegin(); it != g[x].rend(); ++it) {
        int y = *it;
        if (y == p) continue;
        vt[x].suffix[id] = suffix;
        suffix = suffix * t[y];
        id++;
      }
      reverse(vt[x].suffix.begin(), vt[x].suffix.end());
    }
  }
  vector<int> vodd[mn];
  void euler_edge(int x, int p) {
    if (p != -1) {
      if (t[p].sum & 1) {
        vodd[x].push_back(p);
      }
      if (t[x].sum & 1) {
        vodd[p].push_back(x);
      }
    }
    int yid = 0;
    for (auto &y : g[x]) {
      if (y == p) continue;
      S old_tx = t[x];
      t[x] = vt[x].prefix[yid] * vt[x].suffix[yid];
      if (p != -1) {
        t[x] = t[x] * t[p];
      }
      t[x].upd(x);
      euler_edge(y, x);
      t[x] = old_tx;
      yid++;
    }
  }
};
EulerEdge ee;
class TreeSize {
  static const int maxn = mn;

 public:
  int vsize[maxn];
  void rst() {}
  int dfs(int x, int p) {
    int ans = 1;
    for (auto &y : g[x]) {
      if (y == p) continue;
      ans += dfs(y, x);
    }
    vsize[x] = ans;
    return ans;
  }
};
TreeSize tss;
class MatchTree {
 public:
  static const int maxn = mn;
  int match[mn];
  void rst() {}
  bool doMatch(int x, int p) {
    bool matched = false;
    for (auto &y : g[x]) {
      if (y == p) continue;
      if (!doMatch(y, x)) {
        if (matched) {
          assert(false);
        }
        matched = true;
        ;
        match[x] = y;
        match[y] = x;
      }
    }
    return matched;
  }
};
MatchTree mtt;
class CustomDfs {
  static const int maxn = mn;

 public:
  int dpf[maxn][2];
  void f(int x, int p) {
    for (auto &y : g[x]) {
      if (y == p) continue;
      f(y, x);
      int t = (mtt.match[x] == y);
      dpf[x][t] += dpf[y][t ^ 1];
    }
    dpf[x][0]++;
    ;
  }
  long long ans = 0;
  void rst() { ans = 0; }
  void dfs(int x, int p, bool flag = 0) {
    ;
    if ((tss.vsize[x] & 1)) {
      ans += dpf[x][0];
    }
    for (auto &y : g[x]) {
      if (y == p) continue;
      if (flag != (mtt.match[x] == y)) continue;
      dfs(y, x, flag ^ 1);
    }
  }
};
CustomDfs customdfs;
class EulerEdgeM {
  static const int maxn = mn;
  int w[maxn];
  typedef struct S {
    int sum[2];
    int sz = 0;
    S() {
      sum[0] = 0;
      sum[1] = 0;
      sz = 0;
    }
    S(const int &x, const int &y, const int &szz) {
      sum[0] = x;
      sum[1] = y;
      sz = szz;
    }
    S operator*(const S &b) const {
      return S(sum[0] + b.sum[0], sum[1] + b.sum[1], sz + b.sz);
    }
  } S;
  S identity = S(0, 0, 0);
  typedef struct VS {
    vector<S> prefix;
    vector<S> suffix;
  } VS;
  S t[maxn];
  VS vt[maxn];
  void upd(int x, int p) {
    t[x].sum[0] = t[x].sum[1];
    t[x].sum[1] = 0;
    for (auto &y : g[x]) {
      if (y == p) continue;
      if (mtt.match[x] == y) {
        t[x].sum[1] = t[y].sum[0];
      }
    }
    t[x].sum[0]++;
    t[x].sz++;
  }

 public:
  void euler_init(int x, int p) {
    int numchildren = g[x].size() - ((p == -1) ? 0 : 1);
    for (auto &y : g[x]) {
      if (y == p) continue;
      euler_init(y, x);
      t[x] = t[x] * t[y];
    }
    upd(x, p);
    {
      S prefix = identity;
      vt[x].prefix.resize(numchildren);
      int id = 0;
      for (auto &y : g[x]) {
        if (y == p) continue;
        vt[x].prefix[id] = prefix;
        prefix = prefix * t[y];
        id++;
      }
    }
    {
      S suffix = identity;
      vt[x].suffix.resize(numchildren);
      int id = 0;
      for (auto it = g[x].rbegin(); it != g[x].rend(); ++it) {
        int y = *it;
        if (y == p) continue;
        vt[x].suffix[id] = suffix;
        suffix = suffix * t[y];
        id++;
      }
      reverse(vt[x].suffix.begin(), vt[x].suffix.end());
    }
  }
  vector<int> vodd[mn];
  long long finalmatch = 0;
  long long finalun = 0;
  void euler_edge(int x, int p) {
    if (p != -1) {
      long long contrib;
      if (mtt.match[x] != p) {
        int lft = t[x].sz;
        int rt = t[p].sz;
        contrib = lft * (long long)rt;
      } else {
        int lft = (t[x].sum[0]);
        int rt = (t[p].sum[0]);
        contrib = lft * (long long)rt;
      }
      finalmatch += contrib;
    }
    int yid = 0;
    for (auto &y : g[x]) {
      if (y == p) continue;
      S old_tx = t[x];
      t[x] = vt[x].prefix[yid] * vt[x].suffix[yid];
      if (p != -1) {
        t[x] = t[x] * t[p];
      }
      upd(x, y);
      euler_edge(y, x);
      t[x] = old_tx;
      yid++;
    }
  }
};
EulerEdgeM em;
void fail(int t) {
  printf("0\n");
  exit(0);
}
int search(int x, int p, int targ) {
  if (x == targ) return 0;
  for (auto &y : g[x]) {
    if (y == p) continue;
    int got = search(y, x, targ);
    if (got != -1) return got + 1;
  }
  return -1;
}
long long solve(int a, int ap, int b, int bp) {
  mtt.doMatch(a, ap);
  customdfs.rst();
  customdfs.dfs(a, ap);
  long long lft = customdfs.ans;
  mtt.doMatch(b, bp);
  long long rt = customdfs.dpf[b][0];
  return lft * rt;
}
long long head(int a, int ap, int b, int bp) {
  mtt.doMatch(a, ap);
  long long lft = customdfs.dpf[a][0];
  mtt.doMatch(b, bp);
  long long rt = customdfs.dpf[b][0];
  return lft * rt;
}
bitset<mn> bspec;
int search2sum = 0;
vector<int> vg;
bool search2(int x, int p, int targ) {
  if (x == targ) {
    search2sum += bspec[x];
    return true;
  }
  for (auto &y : g[x]) {
    if (y == p) continue;
    int got = search2(y, x, targ);
    if (got) {
      int odds = 0;
      for (auto &z : ee.vodd[x]) {
        if (z == p || z == y) continue;
        odds++;
      }
      if (p != -1) {
        if (odds == 0) {
          vg.push_back(0);
        } else if (odds == 1) {
          vg.push_back(1);
        } else
          fail(10);
      }
      search2sum += bspec[x];
      return true;
    }
  }
  return false;
}
class Diameter {
 public:
  int dist[mn];
  int n;
  void init(int _n) { n = _n; }
  pair<int, int> bfs(int init) {
    if (init == -1) return make_pair(-1, -1);
    for (int x = 1; x <= n; x++) {
      dist[x] = INF;
    }
    queue<int> q;
    q.push(init);
    dist[init] = 0;
    while (!q.empty()) {
      int x = q.front();
      q.pop();
      int cand = dist[x] + 1;
      for (auto &y : g[x]) {
        if (dist[y] > cand) {
          dist[y] = cand;
          q.push(y);
        }
      }
    }
    pair<int, int> ans = make_pair(-1, -1);
    for (int x = 1; x <= n; x++) {
      if (bspec[x]) chkmax(ans, make_pair(dist[x], x));
    }
    return ans;
  }
  pair<int, int> getp(int init) {
    pair<int, int> x = bfs(init);
    pair<int, int> y = bfs(x.second);
    return make_pair(x.second, y.second);
  }
};
Diameter diam;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n = rint();
  if (n & 1) fail(1);
  for (int i = 1; i < n; i++) {
    int x = rint(), y = rint();
    g[x].push_back(y);
    g[y].push_back(x);
  }
  ee.euler_init(1, -1);
  ee.euler_edge(1, -1);
  vector<int> vspec;
  for (int x = 1; x <= n; x++) {
    int sz = ee.vodd[x].size();
    assert(sz & 1);
    if (sz > 3) {
      fail(2);
    } else if (sz > 1) {
      assert(sz == 3);
      bspec[x] = true;
    }
  }
  diam.init(n);
  pair<int, int> ends = diam.getp(1);
  if (ends.first != -1) vspec.push_back(ends.first);
  if (ends.second != -1 && ends.second != ends.first)
    vspec.push_back(ends.second);
  if (vspec.size() > 2) fail(4);
  if (vspec.size() == 1) {
    int special = vspec[0];
    tss.dfs(special, -1);
    for (auto &x : ee.vodd[special]) {
      mtt.doMatch(x, special);
    }
    customdfs.f(special, -1);
    long long final = 0;
    for (auto &x : ee.vodd[special]) {
      for (auto &y : ee.vodd[special]) {
        if (x != y) {
          long long contrib = solve(x, special, y, special);
          final += contrib;
        }
      }
    }
    printf("%lld\n", final);
  } else if (vspec.size() == 2) {
    int special = vspec[0];
    int s2 = vspec[1];
    search2(special, -1, s2);
    if (search2sum != bspec.count()) fail(9);
    tss.dfs(special, -1);
    vector<pair<int, int> > g1, g2, ag;
    bool found = 0;
    for (auto &x : ee.vodd[special]) {
      if (-1 == search(x, special, s2))
        g1.push_back(make_pair(x, special));
      else
        found = 1;
    }
    if (!found) fail(5);
    found = 1;
    for (auto &x : ee.vodd[s2]) {
      if (-1 == search(x, s2, special))
        g2.push_back(make_pair(x, s2));
      else
        found = 1;
    }
    if (!found) fail(6);
    for (auto &x : g1) ag.push_back(x);
    for (auto &x : g2) ag.push_back(x);
    for (auto &x : ag) {
      mtt.doMatch(x.first, x.second);
    }
    customdfs.f(special, -1);
    long long final = 0;
    for (auto &x : g1) {
      for (auto &y : g2) {
        if (x != y) {
          {
            long long contrib = solve(x.first, x.second, y.first, y.second);
            ;
            final += contrib;
          }
          {
            long long contrib = solve(y.first, y.second, x.first, x.second);
            ;
            final += contrib;
          }
        }
      }
    }
    int C = 1;
    int z = 0;
    for (auto &w : vg) {
      if (w == 0)
        z++;
      else {
        if (z != 0) fail(11);
        C++;
      }
      if (z == 2) {
        z = 0;
        C++;
      }
    }
    if (z != 0) fail(12);
    ;
    for (auto &x : g1) {
      for (auto &y : g2) {
        if (x != y) {
          {
            long long contrib = head(x.first, x.second, y.first, y.second);
            final += contrib * C;
          }
        }
      }
    }
    printf("%lld\n", final);
  } else {
    assert(vspec.size() == 0);
    mtt.doMatch(1, -1);
    em.euler_init(1, -1);
    em.euler_edge(1, -1);
    long long ans = em.finalmatch + em.finalun;
    printf("%lld\n", ans);
  }
}
static char stdinBuffer[1024];
static char *stdinDataEnd = stdinBuffer + sizeof(stdinBuffer);
static const char *stdinPos = stdinDataEnd;
void readAhead(size_t amount) {
  size_t remaining = stdinDataEnd - stdinPos;
  if (remaining < amount) {
    memmove(stdinBuffer, stdinPos, remaining);
    size_t sz = fread(stdinBuffer + remaining, 1,
                      sizeof(stdinBuffer) - remaining, stdin);
    stdinPos = stdinBuffer;
    stdinDataEnd = stdinBuffer + remaining + sz;
    if (stdinDataEnd != stdinBuffer + sizeof(stdinBuffer)) *stdinDataEnd = 0;
  }
}
int rint() {
  readAhead(16);
  int x = 0;
  bool neg = false;
  while (*stdinPos == ' ' || *stdinPos == '\n') ++stdinPos;
  if (*stdinPos == '-') {
    ++stdinPos;
    neg = true;
  }
  while (*stdinPos >= '0' && *stdinPos <= '9') {
    x *= 10;
    x += *stdinPos - '0';
    ++stdinPos;
  }
  return neg ? -x : x;
}
char rch() {
  readAhead(16);
  while (*stdinPos == ' ' || *stdinPos == '\n') ++stdinPos;
  char ans = *stdinPos;
  ++stdinPos;
  return ans;
}
long long rlong() {
  readAhead(32);
  long long x = 0;
  bool neg = false;
  while (*stdinPos == ' ' || *stdinPos == '\n') ++stdinPos;
  if (*stdinPos == '-') {
    ++stdinPos;
    neg = true;
  }
  while (*stdinPos >= '0' && *stdinPos <= '9') {
    x *= 10;
    x += *stdinPos - '0';
    ++stdinPos;
  }
  return neg ? -x : x;
}

### Prompt

In CPP, your task is to solve 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;
const int MOD = 1000000007;
const int UNDEF = -1;
const int INF = 1 << 30;
template <typename T>
inline bool chkmax(T &aa, T bb) {
  return aa < bb ? aa = bb, true : false;
}
template <typename T>
inline bool chkmin(T &aa, T bb) {
  return aa > bb ? aa = bb, true : false;
}
int rint();
char rch();
long long rlong();
const int mn = 5e5 + 2;
vector<int> g[mn];
class EulerEdge {
  static const int maxn = mn;
  int w[maxn];
  typedef struct S {
    int sum = 0;
    S() { sum = 0; }
    S(const int &x) { sum = x; }
    S operator*(const S &b) const { return S(sum + b.sum); }
    void upd(int x) { sum++; }
  } S;
  S identity = S(0);
  typedef struct VS {
    vector<S> prefix;
    vector<S> suffix;
  } VS;
  S t[maxn];
  VS vt[maxn];

 public:
  void euler_init(int x, int p) {
    int numchildren = g[x].size() - ((p == -1) ? 0 : 1);
    for (auto &y : g[x]) {
      if (y == p) continue;
      euler_init(y, x);
      t[x] = t[x] * t[y];
    }
    t[x].upd(x);
    {
      S prefix = identity;
      vt[x].prefix.resize(numchildren);
      int id = 0;
      for (auto &y : g[x]) {
        if (y == p) continue;
        vt[x].prefix[id] = prefix;
        prefix = prefix * t[y];
        id++;
      }
    }
    {
      S suffix = identity;
      vt[x].suffix.resize(numchildren);
      int id = 0;
      for (auto it = g[x].rbegin(); it != g[x].rend(); ++it) {
        int y = *it;
        if (y == p) continue;
        vt[x].suffix[id] = suffix;
        suffix = suffix * t[y];
        id++;
      }
      reverse(vt[x].suffix.begin(), vt[x].suffix.end());
    }
  }
  vector<int> vodd[mn];
  void euler_edge(int x, int p) {
    if (p != -1) {
      if (t[p].sum & 1) {
        vodd[x].push_back(p);
      }
      if (t[x].sum & 1) {
        vodd[p].push_back(x);
      }
    }
    int yid = 0;
    for (auto &y : g[x]) {
      if (y == p) continue;
      S old_tx = t[x];
      t[x] = vt[x].prefix[yid] * vt[x].suffix[yid];
      if (p != -1) {
        t[x] = t[x] * t[p];
      }
      t[x].upd(x);
      euler_edge(y, x);
      t[x] = old_tx;
      yid++;
    }
  }
};
EulerEdge ee;
class TreeSize {
  static const int maxn = mn;

 public:
  int vsize[maxn];
  void rst() {}
  int dfs(int x, int p) {
    int ans = 1;
    for (auto &y : g[x]) {
      if (y == p) continue;
      ans += dfs(y, x);
    }
    vsize[x] = ans;
    return ans;
  }
};
TreeSize tss;
class MatchTree {
 public:
  static const int maxn = mn;
  int match[mn];
  void rst() {}
  bool doMatch(int x, int p) {
    bool matched = false;
    for (auto &y : g[x]) {
      if (y == p) continue;
      if (!doMatch(y, x)) {
        if (matched) {
          assert(false);
        }
        matched = true;
        ;
        match[x] = y;
        match[y] = x;
      }
    }
    return matched;
  }
};
MatchTree mtt;
class CustomDfs {
  static const int maxn = mn;

 public:
  int dpf[maxn][2];
  void f(int x, int p) {
    for (auto &y : g[x]) {
      if (y == p) continue;
      f(y, x);
      int t = (mtt.match[x] == y);
      dpf[x][t] += dpf[y][t ^ 1];
    }
    dpf[x][0]++;
    ;
  }
  long long ans = 0;
  void rst() { ans = 0; }
  void dfs(int x, int p, bool flag = 0) {
    ;
    if ((tss.vsize[x] & 1)) {
      ans += dpf[x][0];
    }
    for (auto &y : g[x]) {
      if (y == p) continue;
      if (flag != (mtt.match[x] == y)) continue;
      dfs(y, x, flag ^ 1);
    }
  }
};
CustomDfs customdfs;
class EulerEdgeM {
  static const int maxn = mn;
  int w[maxn];
  typedef struct S {
    int sum[2];
    int sz = 0;
    S() {
      sum[0] = 0;
      sum[1] = 0;
      sz = 0;
    }
    S(const int &x, const int &y, const int &szz) {
      sum[0] = x;
      sum[1] = y;
      sz = szz;
    }
    S operator*(const S &b) const {
      return S(sum[0] + b.sum[0], sum[1] + b.sum[1], sz + b.sz);
    }
  } S;
  S identity = S(0, 0, 0);
  typedef struct VS {
    vector<S> prefix;
    vector<S> suffix;
  } VS;
  S t[maxn];
  VS vt[maxn];
  void upd(int x, int p) {
    t[x].sum[0] = t[x].sum[1];
    t[x].sum[1] = 0;
    for (auto &y : g[x]) {
      if (y == p) continue;
      if (mtt.match[x] == y) {
        t[x].sum[1] = t[y].sum[0];
      }
    }
    t[x].sum[0]++;
    t[x].sz++;
  }

 public:
  void euler_init(int x, int p) {
    int numchildren = g[x].size() - ((p == -1) ? 0 : 1);
    for (auto &y : g[x]) {
      if (y == p) continue;
      euler_init(y, x);
      t[x] = t[x] * t[y];
    }
    upd(x, p);
    {
      S prefix = identity;
      vt[x].prefix.resize(numchildren);
      int id = 0;
      for (auto &y : g[x]) {
        if (y == p) continue;
        vt[x].prefix[id] = prefix;
        prefix = prefix * t[y];
        id++;
      }
    }
    {
      S suffix = identity;
      vt[x].suffix.resize(numchildren);
      int id = 0;
      for (auto it = g[x].rbegin(); it != g[x].rend(); ++it) {
        int y = *it;
        if (y == p) continue;
        vt[x].suffix[id] = suffix;
        suffix = suffix * t[y];
        id++;
      }
      reverse(vt[x].suffix.begin(), vt[x].suffix.end());
    }
  }
  vector<int> vodd[mn];
  long long finalmatch = 0;
  long long finalun = 0;
  void euler_edge(int x, int p) {
    if (p != -1) {
      long long contrib;
      if (mtt.match[x] != p) {
        int lft = t[x].sz;
        int rt = t[p].sz;
        contrib = lft * (long long)rt;
      } else {
        int lft = (t[x].sum[0]);
        int rt = (t[p].sum[0]);
        contrib = lft * (long long)rt;
      }
      finalmatch += contrib;
    }
    int yid = 0;
    for (auto &y : g[x]) {
      if (y == p) continue;
      S old_tx = t[x];
      t[x] = vt[x].prefix[yid] * vt[x].suffix[yid];
      if (p != -1) {
        t[x] = t[x] * t[p];
      }
      upd(x, y);
      euler_edge(y, x);
      t[x] = old_tx;
      yid++;
    }
  }
};
EulerEdgeM em;
void fail(int t) {
  printf("0\n");
  exit(0);
}
int search(int x, int p, int targ) {
  if (x == targ) return 0;
  for (auto &y : g[x]) {
    if (y == p) continue;
    int got = search(y, x, targ);
    if (got != -1) return got + 1;
  }
  return -1;
}
long long solve(int a, int ap, int b, int bp) {
  mtt.doMatch(a, ap);
  customdfs.rst();
  customdfs.dfs(a, ap);
  long long lft = customdfs.ans;
  mtt.doMatch(b, bp);
  long long rt = customdfs.dpf[b][0];
  return lft * rt;
}
long long head(int a, int ap, int b, int bp) {
  mtt.doMatch(a, ap);
  long long lft = customdfs.dpf[a][0];
  mtt.doMatch(b, bp);
  long long rt = customdfs.dpf[b][0];
  return lft * rt;
}
bitset<mn> bspec;
int search2sum = 0;
vector<int> vg;
bool search2(int x, int p, int targ) {
  if (x == targ) {
    search2sum += bspec[x];
    return true;
  }
  for (auto &y : g[x]) {
    if (y == p) continue;
    int got = search2(y, x, targ);
    if (got) {
      int odds = 0;
      for (auto &z : ee.vodd[x]) {
        if (z == p || z == y) continue;
        odds++;
      }
      if (p != -1) {
        if (odds == 0) {
          vg.push_back(0);
        } else if (odds == 1) {
          vg.push_back(1);
        } else
          fail(10);
      }
      search2sum += bspec[x];
      return true;
    }
  }
  return false;
}
class Diameter {
 public:
  int dist[mn];
  int n;
  void init(int _n) { n = _n; }
  pair<int, int> bfs(int init) {
    if (init == -1) return make_pair(-1, -1);
    for (int x = 1; x <= n; x++) {
      dist[x] = INF;
    }
    queue<int> q;
    q.push(init);
    dist[init] = 0;
    while (!q.empty()) {
      int x = q.front();
      q.pop();
      int cand = dist[x] + 1;
      for (auto &y : g[x]) {
        if (dist[y] > cand) {
          dist[y] = cand;
          q.push(y);
        }
      }
    }
    pair<int, int> ans = make_pair(-1, -1);
    for (int x = 1; x <= n; x++) {
      if (bspec[x]) chkmax(ans, make_pair(dist[x], x));
    }
    return ans;
  }
  pair<int, int> getp(int init) {
    pair<int, int> x = bfs(init);
    pair<int, int> y = bfs(x.second);
    return make_pair(x.second, y.second);
  }
};
Diameter diam;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n = rint();
  if (n & 1) fail(1);
  for (int i = 1; i < n; i++) {
    int x = rint(), y = rint();
    g[x].push_back(y);
    g[y].push_back(x);
  }
  ee.euler_init(1, -1);
  ee.euler_edge(1, -1);
  vector<int> vspec;
  for (int x = 1; x <= n; x++) {
    int sz = ee.vodd[x].size();
    assert(sz & 1);
    if (sz > 3) {
      fail(2);
    } else if (sz > 1) {
      assert(sz == 3);
      bspec[x] = true;
    }
  }
  diam.init(n);
  pair<int, int> ends = diam.getp(1);
  if (ends.first != -1) vspec.push_back(ends.first);
  if (ends.second != -1 && ends.second != ends.first)
    vspec.push_back(ends.second);
  if (vspec.size() > 2) fail(4);
  if (vspec.size() == 1) {
    int special = vspec[0];
    tss.dfs(special, -1);
    for (auto &x : ee.vodd[special]) {
      mtt.doMatch(x, special);
    }
    customdfs.f(special, -1);
    long long final = 0;
    for (auto &x : ee.vodd[special]) {
      for (auto &y : ee.vodd[special]) {
        if (x != y) {
          long long contrib = solve(x, special, y, special);
          final += contrib;
        }
      }
    }
    printf("%lld\n", final);
  } else if (vspec.size() == 2) {
    int special = vspec[0];
    int s2 = vspec[1];
    search2(special, -1, s2);
    if (search2sum != bspec.count()) fail(9);
    tss.dfs(special, -1);
    vector<pair<int, int> > g1, g2, ag;
    bool found = 0;
    for (auto &x : ee.vodd[special]) {
      if (-1 == search(x, special, s2))
        g1.push_back(make_pair(x, special));
      else
        found = 1;
    }
    if (!found) fail(5);
    found = 1;
    for (auto &x : ee.vodd[s2]) {
      if (-1 == search(x, s2, special))
        g2.push_back(make_pair(x, s2));
      else
        found = 1;
    }
    if (!found) fail(6);
    for (auto &x : g1) ag.push_back(x);
    for (auto &x : g2) ag.push_back(x);
    for (auto &x : ag) {
      mtt.doMatch(x.first, x.second);
    }
    customdfs.f(special, -1);
    long long final = 0;
    for (auto &x : g1) {
      for (auto &y : g2) {
        if (x != y) {
          {
            long long contrib = solve(x.first, x.second, y.first, y.second);
            ;
            final += contrib;
          }
          {
            long long contrib = solve(y.first, y.second, x.first, x.second);
            ;
            final += contrib;
          }
        }
      }
    }
    int C = 1;
    int z = 0;
    for (auto &w : vg) {
      if (w == 0)
        z++;
      else {
        if (z != 0) fail(11);
        C++;
      }
      if (z == 2) {
        z = 0;
        C++;
      }
    }
    if (z != 0) fail(12);
    ;
    for (auto &x : g1) {
      for (auto &y : g2) {
        if (x != y) {
          {
            long long contrib = head(x.first, x.second, y.first, y.second);
            final += contrib * C;
          }
        }
      }
    }
    printf("%lld\n", final);
  } else {
    assert(vspec.size() == 0);
    mtt.doMatch(1, -1);
    em.euler_init(1, -1);
    em.euler_edge(1, -1);
    long long ans = em.finalmatch + em.finalun;
    printf("%lld\n", ans);
  }
}
static char stdinBuffer[1024];
static char *stdinDataEnd = stdinBuffer + sizeof(stdinBuffer);
static const char *stdinPos = stdinDataEnd;
void readAhead(size_t amount) {
  size_t remaining = stdinDataEnd - stdinPos;
  if (remaining < amount) {
    memmove(stdinBuffer, stdinPos, remaining);
    size_t sz = fread(stdinBuffer + remaining, 1,
                      sizeof(stdinBuffer) - remaining, stdin);
    stdinPos = stdinBuffer;
    stdinDataEnd = stdinBuffer + remaining + sz;
    if (stdinDataEnd != stdinBuffer + sizeof(stdinBuffer)) *stdinDataEnd = 0;
  }
}
int rint() {
  readAhead(16);
  int x = 0;
  bool neg = false;
  while (*stdinPos == ' ' || *stdinPos == '\n') ++stdinPos;
  if (*stdinPos == '-') {
    ++stdinPos;
    neg = true;
  }
  while (*stdinPos >= '0' && *stdinPos <= '9') {
    x *= 10;
    x += *stdinPos - '0';
    ++stdinPos;
  }
  return neg ? -x : x;
}
char rch() {
  readAhead(16);
  while (*stdinPos == ' ' || *stdinPos == '\n') ++stdinPos;
  char ans = *stdinPos;
  ++stdinPos;
  return ans;
}
long long rlong() {
  readAhead(32);
  long long x = 0;
  bool neg = false;
  while (*stdinPos == ' ' || *stdinPos == '\n') ++stdinPos;
  if (*stdinPos == '-') {
    ++stdinPos;
    neg = true;
  }
  while (*stdinPos >= '0' && *stdinPos <= '9') {
    x *= 10;
    x += *stdinPos - '0';
    ++stdinPos;
  }
  return neg ? -x : x;
}

```