Problem: You are given a tree with n vertices numbered 1, …, n. A tree is a connected simple graph without cycles.

Let dist(u, v) be the number of edges in the unique simple path connecting vertices u and v.

Let diam(l, r) = max dist(u, v) over all pairs u, v such that l ≤ u, v ≤ r.

Compute ∑_{1 ≤ l ≤ r ≤ n} diam(l, r).

Input

The first line contains a single integer n (1 ≤ n ≤ 10^5) — the number of vertices in the tree.

The next n - 1 lines describe the tree edges. Each of these lines contains two integers u, v (1 ≤ u, v ≤ n) — endpoint indices of the respective tree edge. It is guaranteed that the edge list indeed describes a tree.

Output

Print a single integer — ∑_{1 ≤ l ≤ r ≤ n} diam(l, r).

Examples

Input


4
1 2
2 4
3 2


Output


10


Input


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


Output


224

Solution (in CPP):

Solution:

// stay simple, stay naive

#include <stdint.h>
#include <stdbool.h>
#include <stdarg.h>
#include <stdalign.h>
#include <complex.h>

#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <time.h>

#include <stdio.h>
#include <assert.h>
#ifdef _LOCAL_JUDGE
#define eprintf(...)                                      \
  ({                                                      \
    fprintf(stderr, __VA_ARGS__);                         \
    fflush(stderr);                                       \
    0;                                                    \
  })
#else
#define eprintf(...) 0
#endif

#define swap(x, y)                                        \
  ((void)({                                               \
    __typeof(x) _tmp##__COUNTER__ = x;                    \
    x = y; y = _tmp##__COUNTER__; 0;                      \
  }))
#define max(x, y)                                         \
  ({                                                      \
    __typeof(x) _X##__COUNTER__ = x;                      \
    __typeof(y) _Y##__COUNTER__ = y;                      \
    ((_X##__COUNTER__) > (_Y##__COUNTER__))               \
      ? (_X##__COUNTER__)                                 \
      : (_Y##__COUNTER__);                                \
  })

#define Maxn ((int)2e5 + 5)
#define LOG 20

int n;
int64_t ans;
typedef struct {
  int to, nxt;
} Edge;
Edge e[Maxn << 1];
int edge_num, head_edge[Maxn];
void clear_graph(int n) {
  edge_num = 0;
  memset(e, 0, sizeof(*e) * n);
  memset(head_edge, -1, sizeof(*head_edge) * n);
}
__attribute__((__always_inline__))
__inline void add_edge(int u, int v) {
  e[edge_num] = (Edge) {
    .to = v, 
    .nxt = head_edge[u]
  };
  head_edge[u] = edge_num++;
}
#define for_each_edge(u, i)                             \
  for (int i = head_edge[(u)]; i != -1; i = e[i].nxt)
  
int par[Maxn][LOG], dep[Maxn];
void lca_dfs(int u, int fa, int depth) {
  dep[u] = depth; par[u][0] = fa;
  for (int j = 1; j < LOG; ++j)
    par[u][j] = ((par[u][j - 1] == -1) ? -1 : par[par[u][j - 1]][j - 1]);
  for_each_edge(u, i)
    if (e[i].to != fa)
      lca_dfs(e[i].to, u, depth + 1);
}
__attribute__((__always_inline__))
__inline void lca_init(int root) {
  lca_dfs(root, -1, 0);
}
int jump_up(int u, int d) {
  for (; d && ~u; d &= d - 1)
    u = par[u][__builtin_ctz(d)];
  return u;
}
int get_lca(int u, int v) {
  if (dep[u] < dep[v]) swap(u, v);
  u = jump_up(u, dep[u] - dep[v]);
  if (u == v) return u;
  for (int j = LOG - 1; j >= 0; --j)
    if (par[u][j] != par[v][j])
      u = par[u][j], v = par[v][j];
  return par[u][0];
}
__attribute__((__always_inline__))
__inline int distance(int u, int v) {
  return dep[u] + dep[v] - 2 * dep[get_lca(u, v)];
}
__attribute__((__always_inline__))
__inline int jump_to(int x, int y, int d) {
  int z = get_lca(x, y), dist = dep[x] - dep[z];
  if (dist >= d) return jump_up(x, d);
  else return jump_up(y, (dep[y] - dep[z]) - (d - dist));
}

int v_root, v_tot;
int v_mx[Maxn], v_sz[Maxn];
bool v_vis[Maxn];
int v_cur;
typedef struct {
  int u, cur, d;
} anc_info;
anc_info anc[Maxn][LOG];
int anc_siz[Maxn];
void v_get_root(int u, int fa) {
  v_mx[u] = 0, v_sz[u] = 1;
  for_each_edge(u, i) {
    if (e[i].to != fa && v_vis[e[i].to] == false) {
      v_get_root(e[i].to, u);
      v_sz[u] += v_sz[e[i].to];
      v_mx[u] = max(v_mx[u], v_sz[e[i].to]);
    }
  }
  v_mx[u] = max(v_mx[u], v_tot - v_sz[u]);
  if (v_root == -1 || v_mx[u] < v_mx[v_root])
    v_root = u;
}
void v_dfs(int u, int fa, int d) {
  anc[u][anc_siz[u]++] = (anc_info){v_root, v_cur, d};
  for_each_edge(u, i)
    if (e[i].to != fa && v_vis[e[i].to] == false)
      v_dfs(e[i].to, u, d + 1);
}
void v_divide(int u) {
  v_vis[v_root = u] = true;
  anc[u][anc_siz[u]++] = (anc_info){u, 0, 0};
  for_each_edge(u, i)
    if (v_vis[e[i].to] == false)
      v_cur++, v_dfs(e[i].to, u, 1);
  for_each_edge(u, i) {
    if (v_vis[e[i].to] == false) {
      v_tot = v_sz[e[i].to];
      v_root = -1;
      v_get_root(e[i].to, -1);
      v_divide(v_root);
    }
  }
}
__attribute__((__always_inline__))
__inline void virtual_tree_init(int n) {
  memset(v_vis, false, sizeof(v_vis));
  v_tot = n; 
  v_root = -1; v_get_root(0, -1);
  v_cur = 0;
  v_divide(v_root);
}

int64_t s1[Maxn], s2[Maxn], s3[Maxn], s4[Maxn];
void modify(int x, int val) {
  for (int i = 0; i < anc_siz[x]; ++i) {
    s1[anc[x][i].u] += anc[x][i].d * val;
    s2[anc[x][i].cur] += anc[x][i].d * val;
    s3[anc[x][i].u] += val;
    s4[anc[x][i].cur] += val;
  }
}
int64_t query(int x) {
  int64_t res = 0;
  for (int i = 0; i < anc_siz[x]; ++i) {
    res += (s1[anc[x][i].u] - s2[anc[x][i].cur]);
    res += (s3[anc[x][i].u] - s4[anc[x][i].cur]) * anc[x][i].d;
  }
  return res;
}

typedef struct {
  int center, radium;
} circ;
__attribute__((__always_inline__))
__inline circ join(circ x, circ y) {
  if (x.radium < y.radium) swap(x, y);
  int d = distance(x.center, y.center);
  if (d <= x.radium - y.radium) return x;
  else { // d > x.radium - y.radium
    int new_radium = (d + x.radium + y.radium) / 2;
    int new_center = jump_to(x.center, y.center, new_radium - x.radium);
    return (circ){.center = new_center, .radium = new_radium};
  }
}
__attribute__((__always_inline__))
__inline int compare(circ x, circ y) {
  int ceof = (x.radium < y.radium) ? (swap(x, y), -1) : 1;
  return (distance(x.center, y.center) <= x.radium - y.radium) ? ceof : 0;
}
void divide(int l, int r) {
  if (l + 1 == r) return ;
  int mid = (l + r) >> 1;
  divide(l, mid); divide(mid, r);
  static circ c[Maxn] = { };
  static int64_t suf[Maxn] = { };
  c[mid - 1] = (circ){mid - 1, 0};
  c[mid] = (circ){mid, 0};
  for (int i = mid + 1; i < r; ++i)
    c[i] = join(c[i - 1], (circ){i, 0});
  suf[r] = 0;
  for (int i = r - 1; i >= mid; --i)
    suf[i] = suf[i + 1] + c[i].radium;
  int p1 = mid, p2 = mid;
  for (int i = mid - 1; i >= l; --i) {
    while (p2 < r && compare(c[i], c[p2]) != -1)
      modify(c[p2++].center, 1);
    while (p1 < p2 && compare(c[i], c[p1]) == 1)
      modify(c[p1++].center, -1);
    ans += 2ll * c[i].radium * (p1 - mid) + 1ll * c[i].radium * (p2 - p1);
    ans += suf[p1] + suf[p2] + query(c[i].center);
    if (i > l) c[i - 1] = join(c[i], (circ){i - 1, 0});
  }
  while (p1 < p2) modify(c[p1++].center, -1);
}

int32_t main() {

  scanf("%d", &n);
  clear_graph(n * 2 - 1);
  for (int i = 0; i < n - 1; ++i) {
    int u, v;
    scanf("%d%d", &u, &v);
    --u, --v;
    add_edge(u, n + i);
    add_edge(n + i, u);
    add_edge(v, n + i);
    add_edge(n + i, v);
  }
  lca_init(0);
  virtual_tree_init(n * 2 - 1);
  ans = (int64_t)0;
  divide(0, n);
  assert(ans % 2 == 0);
  ans /= 2;
  printf("%lld\n", ans);

  exit(EXIT_SUCCESS);

} // main()