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:
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
#define int ll
using ll = long long;
vector<int> v[N];int sz[N];
bool vis[N];
void dfs(int pos,int fa)
{ sz[pos] = 1;for (auto &i : v[pos]) if (i != fa && !vis[i]) dfs(i,pos),sz[pos] += sz[i]; }
int dp[N][20],dep[N];
void dfs2(int pos,int fa)
{
    dep[pos] = dep[fa] + 1;dp[pos][0] = fa;
    for (int i = 1;(1 << i) <= dep[pos];i++) dp[pos][i] = dp[dp[pos][i - 1]][i - 1];
    for (auto &i : v[pos]) if (i != fa) dfs2(i,pos);
}
int f[20][N];
void dfs3(int pos,int fa,int r)
{ for (auto &i : v[pos]) if (i != fa && !vis[i]) f[r][i] = f[r][pos] + 1,dfs3(i,pos,r); }
int kk,mn,rt;
void getrt(int pos,int fa)
{
    int vv = kk - sz[pos];
    for (auto &i : v[pos]) if (i != fa && !vis[i]) getrt(i,pos),vv = max(vv,sz[i]);
    if (vv < mn) rt = pos,mn = vv;
}
int g[N],ff[N];
void dfs4(int pos,int fa)
{
    dfs(pos,0);mn = kk = sz[pos];getrt(pos,0);
    vis[pos = rt] = 1;g[pos] = g[ff[pos] = fa] + 1;dfs3(pos,0,g[pos]);
    for (auto &i : v[pos]) if (!vis[i]) dfs4(i,pos);
}
int lca(int x,int y)
{
    if (dep[x] < dep[y]) swap(x,y);
    for (int i = 19;i >= 0;--i)
        if (dep[dp[x][i]] >= dep[y]) x = dp[x][i];
    if (x == y) return x;
    for (int i = 19;i >= 0;--i)
        if (dp[x][i] != dp[y][i]) x = dp[x][i],y = dp[y][i];
    return dp[x][0];
}
inline int dis(int x,int y) {return dep[x] + dep[y] - 2 * dep[lca(x,y)];}
ll w[N],b[N],c[N];
void ins(int pos,int x)
{
    for (int i = pos,j = g[pos];i > 0;i = ff[i],--j)
    {
        if (j > 1) w[i] += x * f[j - 1][pos];
        b[i] += x * f[j][pos];c[i] += x;
    }
}
ll query(int pos)
{
    ll ans = b[pos];
    for (int i = pos,j = ff[pos],k = g[pos] - 1;j > 0;i = j,j = ff[j],--k)
        ans += (c[j] - c[i]) * f[k][pos] + b[j] - w[i];
    return ans;
}
int lift(int pos,int d)
{
    for (int i = 19;i >= 0;--i) if (d & (1 << i)) pos = dp[pos][i];
    return pos;
}
int get_center(int x,int y,int d)
{
    int t = lca(x,y);if (dep[x] - dep[t] >= d) return lift(x,d);
    return lift(y,dep[y] - dep[t] - (d - (dep[x] - dep[t])));
}
struct Node {int p,r;} a[N];
Node merge(Node a,Node b)
{
    int d = dis(a.p,b.p);if (b.r + d <= a.r) return a;else if (a.r + d <= b.r) return b;
    return {get_center(a.p,b.p,(a.r + d + b.r) / 2 - a.r),(a.r + d + b.r) / 2}; 
}
inline bool check1(int x,int y) {return a[x].r + dis(a[x].p,a[y].p) <= a[y].r;}
inline bool check2(int x,int y) {return a[x].r + dis(a[x].p,a[y].p) < a[y].r;}
ll ans = 0;int suf[N];
void solve(int l,int r)
{
    if (l == r) return;
    int mid = (l + r) >> 1;a[mid] = {mid,0};
    for (int i = mid - 1;i >= l;--i) a[i] = merge(a[i + 1],{i,0});
    a[mid + 1] = {mid + 1,0};
    for (int i = mid + 2;i <= r;i++) a[i] = merge(a[i - 1],{i,0});
    int lp = mid,rp = mid + 1;suf[r + 1] = 0;
    for (int i = r;i >= mid;--i) suf[i] = suf[i + 1] + a[i].r;
    for (int i = mid;i >= l;--i)
    {
        while (rp <= r && !check1(i,rp)) ins(a[rp++].p,1);
        while (lp < r && check2(lp + 1,i)) ins(a[++lp].p,-1);
        ans += suf[rp] + ll(lp - mid) * a[i].r +
               (suf[lp + 1] - suf[rp] + ll(rp - lp - 1) * a[i].r + query(a[i].p)) / 2;
    }
    while (lp + 1 < rp) ins(a[++lp].p,-1);
    solve(l,mid);solve(mid + 1,r);
}
int n;
inline void add_edge(int uu,int vv) {v[uu].push_back(vv);v[vv].push_back(uu);}
signed main ()
{
    ios::sync_with_stdio(false);
    cin >> n;int t1,t2;
    for (int i = 1;i < n;i++) cin >> t1 >> t2,add_edge(t1,i + n),add_edge(i + n,t2);
    dfs2(1,0);dfs4(1,0);
    solve(1,n);cout << ans << endl;
    return 0;
}