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>
#define ll long long
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mid ((l+r)>>1)
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r
#define fors(i, a, b) for(int i = (a); i < (b); ++i)
using namespace std;
const int maxn = 2e5 + 5;
int sz[maxn],  top[maxn], son[maxn], dep[maxn], fa[maxn];
int dfn[maxn], id[maxn], idx = 0;
vector<int> g[maxn];
void dfs1(int u){//sz, fa, dep, son
    sz[u] = 1;
    for(int v:g[u]){
        if(v == fa[u]) continue;
        dep[v] = dep[u]+1; fa[v] = u;
        dfs1(v); sz[u] += sz[v];
        if(sz[son[u]] < sz[v]) son[u] = v;
    }return;
}
void dfs2(int u, int tp){//dfn,id,top
    dfn[id[u] = ++idx] = u;
    top[u] = tp; if(son[u]) dfs2(son[u], tp);
    for(int v: g[u]){
        if(v == fa[u]||v==son[u]) continue;
        dfs2(v, v);
    }
}
inline int lca(int u, int v){
    while (top[u] != top[v]) {
        if (dep[top[u]] > dep[top[v]]) u = fa[top[u]];
        else v = fa[top[v]];
    }
    return dep[u] < dep[v] ? u : v;
}
int dist(int u, int v){return dep[u]+dep[v]-2*dep[lca(u,v)]; }
struct Dia{
    int u, v, d;
    Dia(int _u=0, int _v=0, int _d=-1) : u(_u), v(_v), d(_d) {}
    bool operator == (const Dia & a) const {
        return (u == a.u && v == a.v||u==a.v && v == a.u);
    }
    bool operator != (const Dia & a) const {return !(*this == a);}
    Dia operator + (const Dia & a) const {
        if (a.d == -1) return *this;
        if (d == -1) return a;
        Dia c = (d < a.d ? a : *this);
        for (auto x : {u, v}) {
            for (auto y : {a.u, a.v}) {
                int d = dist(x, y);
                if (d > c.d) c = Dia(x, y, d);
            }
        }
        return c;
    }
};
int get_center(Dia x){
    int u = x.u,v = x.v; if(u == v) return u;
    if(dep[u] == dep[v]) return lca(u,v);
    if(dep[u] < dep[v]) swap(u, v);
    int cur = u;
    while( 2*(dep[u]-dep[fa[top[cur]]] ) <= x.d ) cur = fa[top[cur]];
    int l = id[top[cur]], r = id[cur];
    int res = -1;
    while(l <= r){
        int p = dfn[mid];
        if((dep[u]-dep[p])*2 <= x.d) res = p, r = mid-1;
        else l = mid+1;
    }
    assert(res != -1);
    return res;
}
int n;
void add(int x, int y){g[x].pb(y); g[y].pb(x);}
namespace tree{
    int lz[maxn<<2];ll sum[maxn<<2];
    void down(int rt, int l, int r){
        if(lz[rt]){
            lz[rt<<1] += lz[rt];
            lz[rt<<1|1] += lz[rt];
            sum[rt<<1] += lz[rt] * (ll)(mid-l+1);
            sum[rt<<1|1] += lz[rt]*(ll)(r-mid);
            lz[rt] = 0;
        }
    }
    void add(int rt, int l, int r, int L, int R, int x){
        if(L <= l && r <= R) {
            lz[rt] += x; sum[rt] += x * (r-l+1); return;
        }down(rt, l, r);
        if(L <= mid) add(lson , L, R, x);
        if(R > mid) add(rson, L, R, x);
        sum[rt] = sum[rt<<1] + sum[rt<<1|1];
        return;
    }
    ll qry(int rt, int l, int r, int L, int R){
        if(L <= l && r <= R) return sum[rt];
        down(rt,l,r); ll res = 0;
        if(L <= mid) res += qry(lson, L, R);
        if(R > mid) res += qry(rson, L, R); return res;
    }
}
Dia e[maxn];
ll sumd[maxn];
ll sum_dep = 0, sum_sz = 0;
void del(int x){
    sum_sz--; sum_dep -= dep[x];
    while(x) tree::add(1,1,idx,id[top[x]], id[x], -2), x = fa[top[x]];
}
void add(int x){
    sum_sz++; sum_dep += dep[x];
    while(x) tree::add(1,1,idx,id[top[x]], id[x], 2), x = fa[top[x]];
}
ll qry(int x){
    ll res = sum_sz*dep[x] + sum_dep;
    while(x) res -= (tree::qry(1,1,idx,id[top[x]],id[x])), x = fa[top[x]];
    return res;
}
int cen[maxn];
ll sol(int l, int r){
    if(l == r) return 0;
    ll ans = 0;
    ans += sol(l, mid); ans += sol(mid+1, r);
    assert(sum_dep == 0 && sum_sz == 0);
    e[mid] = Dia(mid,mid,0);
    for(int i = mid-1; i >= l; --i) e[i] = Dia(i,i,0)+e[i+1];
    e[mid+1] = Dia(mid+1, mid+1, 0);
    sumd[mid] = sumd[mid+1] = 0;
    for(int i = mid+2; i <= r; ++i) e[i] = e[i-1] + Dia(i,i,0), sumd[i] = sumd[i-1]+e[i].d;
    int p1 = mid+1, p2 = mid;

    for(int i = mid; i >= l; --i){
        int c1 = get_center(e[i]);
        while(p2+1 <= r){
            int c2 = get_center(e[p2+1]);
            cen[p2+1] = c2;
            if( (e[i]+e[p2+1]).d*2 == e[i].d + e[p2+1].d + 2*dist(c1, c2) ) add(c2), ++p2;
            else break;
        }
        while(p1 <= r && (e[i]+e[p1]).d == e[i].d) {
            int c = get_center(e[p1]);
            del(c); p1++;
        }

        ans += (ll)(p1-mid-1) * e[i].d;
        ans += sumd[r]-sumd[p2];
        ans += (p2-p1+1) * (ll)(e[i].d/2) + (sumd[p2]-sumd[p1-1])/2;
        ans += qry(c1);
    }
    while(p1 <= p2) del(cen[p1]), p1++;
    return ans;
}
int main()
{
    scanf("%d", &n); fors(i,1,n) {
        int u,v;
        scanf("%d%d",&u,&v);
        add(n+i,u); add(n+i, v);
    }
    dep[1] = 1;
    dfs1(1); dfs2(1,1);
    //fors(i,1,idx+1) cout<<dfn[i]<<" ";cout<<endl;
    cout<<sol(1,n)/2<<endl;
	return 0;
}