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:
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC option("arch=native","tune=native","no-zero-upper")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#define INF 2147483647
#define infL (1LL<<60)
#define inf (1<<30)
#define inf9 (1000000000)
#define MOD 998244353//1000000007
#define EPS 1e-9
#define Gr 9.8
#define PI acos(-1)
#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define REQ(i,n) for(int (i)=1;(i)<=(int)(n);(i)++)
#define lch (rt<<1)
#define rch (rt<<1|1)
#define readmp(n) for(int i=0,u,v;i<n;i++) {scanf("%d%d",&u,&v); mp[u].push_back(v); mp[v].push_back(u);}
typedef  long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef ld ValType;
template<typename  T> void maxtt(T& t1, T t2) {
    t1=max(t1,t2);
}
template<typename  T> void mintt(T& t1, T t2) {
    t1=min(t1,t2);
}
#define MAX (200135)

bool debug = 0;
int n,m,k;
int dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0};
string direc="RDLU";
const ll MOD2 = (ll)MOD * (ll)MOD;
ll ln, lk, lm;
void etp(bool f = 0) {
    puts(f ?"YES" : "NO");
    exit(0);
}
void addmod(int &x, int y, int mod = MOD){
    x+=y; if (x>=mod) x-=mod;
    if(x<0) x+=mod;
    assert(x>=0 && x<mod);
}
void et(int x=-1) {
    printf("%d\n", x); exit(0);
}
ll fastPow(ll x, ll y, int mod=MOD) {
    ll ans = 1;
    while(y>0) {
        if(y&1) ans = (x * ans)%mod;
        x = x*x%mod;
        y>>=1;
    }
    return ans;
}
ll gcd1(ll x, ll y) {
    return y?gcd1(y,x%y):x;
}


vector<int> mp[MAX];
int d[MAX], p[MAX][20];
void addE(int u, int v) {
    mp[u].push_back(v);
    mp[v].push_back(u);
}
void dfs(int x, int pa) {
    d[x]=d[pa]+1; p[x][0]=pa;
    for(int c:mp[x]) if(c!=pa) dfs(c, x);
}
void initlca(int n){
    for(int j=1; (1<<j)<=n; j++)
        for(int i=1; i<=n; i++)
            p[i][j]=p[p[i][j-1]][j-1];
}
int lca(int a,int b) {
    if(d[a]>d[b])swap(a,b);
    int f=d[b]-d[a];
    for(int i=0; (1<<i)<=f; i++)
        if((1<<i)&f)b=p[b][i];
    if(a!=b) {
        for(int i=19; i>=0; i--)
            if(p[a][i]!=p[b][i]) {
                a=p[a][i]; b=p[b][i];
            }
        a=p[a][0];
    }
    return a;
}
int dist(int a, int b) {
    return d[a]+d[b]-2*d[lca(a, b)];
}
inline int kthfa(int x, int k){
    int td = d[x]-k;
    for(int j=19;j>=0;j--) {
        if (d[p[x][j]] >= td) {
            x=p[x][j];
        }
    }
    return x;
}
int walk(int x,int y,int stp){
    if (stp==0) return x;
    int L=lca(x,y);
    if (d[x]-d[L]>=stp)
        return kthfa(x,stp);
    return kthfa(y,(d[y]+d[x]-2*d[L])-stp);
}
struct ctt {
    int sz[MAX];
    bool vis[MAX];
    void calSize(int x, int pa) {
        sz[x]=1;
        for(int c : mp[x]) if (c!=pa && !vis[c]) {
            calSize(c,x);
            sz[x]+=sz[c];
        }
    }
    int center(int x) {
        calSize(x, -1);
        int cap = sz[x] / 2;
        bool fg = 0; int pa=-1;
        while(1) {
            fg=0;
            for(auto c :mp[x]) if (c != pa && !vis[c]) {
                if (sz[c] > cap) {
                    fg=1; pa=x; x=c; break;
                }
            }
            if (!fg) return x;
        }
    }
    
    
    int layer[MAX];
    int dep[20][MAX], subId[20][MAX];
    int cpa[MAX];
    vector<ll> ts[MAX]; ll tsAll[MAX];
    vector<int> cnt[MAX]; int cntAll[MAX];
    
    int dfs(int u,int p,int d,int l,int s) {
        dep[l][u] = d; subId[l][u] = s;
        for (int v: mp[u]) {
            if (!vis[v] && (v != p)) dfs(v,u,d+1,l,s);
        }
        return 0;
    }
    inline int build(int x, int L) {
        int C=center(x);
        vis[C]=1; layer[C] = L;
        int idx=0;
        for (int v: mp[C]) if (!vis[v]) {
            dfs(v,C,1,L,idx++);
            v = build(v,L+1);
            cpa[v] = C;
        }
        ts[C].resize(idx,0);
        cnt[C].resize(idx, 0);
        return C;
    }
    void init() {
        build(1, 0);
        
    }
    
    
    void add(int x, int fg) {
        int y=x; cntAll[x]+=fg;
        while (x) {
           
            int f = cpa[x]; if(f==0) break;
             int L=layer[f];
            
            cnt[f][subId[L][y]]+=fg;
            cntAll[f]+=fg;
            ts[f][subId[L][y]]+=dep[L][y] * fg;
            tsAll[f]+=dep[L][y] * fg;
            x=f;
        }
    }
    ll qy(int x) {
        ll tt=tsAll[x]; int y=x;
        while (x) {
           
            int f = cpa[x]; if(f==0) break;
            int L=layer[f];
            int cc=cntAll[f] - cnt[f][subId[L][y]];
            ll ps = tsAll[f] - ts[f][subId[L][y]];
            ll cur = dep[L][y];
            tt += cur * cc + ps;
            x=f;
        }
        return tt;
    }
}T;
ll Ans;
struct mb {
    int v;
    int r;
    bool contains(mb o) {
        return dist(v,o.v) <= r - o.r;
    }
};
mb mg(mb a, mb b) {
    if (a.contains(b)) return a;
    if (b.contains(a)) return b;
    int r = (a.r+b.r+dist(a.v, b.v))/2;
    int C=walk(a.v, b.v, r-a.r);
    return {C,r};
}
inline void cal(int l, int r) {
    if(l==r) return;
    int mid=(l+r)/2;
    vector<mb> cL, cR;
    for(int i=mid+1;i<=r;i++) {
        mb tmp = {i, 0};
        if (cR.empty()) cR.push_back(tmp);
        else cR.push_back(mg(cR.back(), tmp));
    }
    for(int i=mid;i>=l;i--) {
        mb tmp = {i, 0};
        if (cL.empty()) cL.push_back(tmp);
        else cL.push_back(mg(cL.back(), tmp));
    }
    int sL=(int)cL.size(), sR = (int)cR.size();
    vector<ll> ps(sR+1, 0);
    REP(i, sR) ps[i+1]=ps[i]+cR[i].r;
    int p=0,q=0;
    for(int i=0;i<sL;i++) {
        while (q<sR && !cR[q].contains(cL[i])) {
            T.add(cR[q].v, 1);
            q++;
        }
        while (p<sR && p<q && cL[i].contains(cR[p])) {
            T.add(cR[p].v, -1); p++;
        }
        Ans +=  2LL * p* cL[i].r;
        Ans += 2LL * (ps[sR]-ps[q]);
        Ans += T.qy(cL[i].v) ;
        Ans += (ll)cL[i].r * (q-p) + ps[q]-ps[p];
        
        int zzz=0;
    }
    while (p<q) {
        T.add(cR[p].v, -1); p++;
    }
    cal(l, mid); cal(mid+1, r);
}
void fmain(int tid) {
    scanf("%d", &n);
    int t=n+1;
    REQ(i,n-1) {
        int u,v; scanf("%d%d", &u,&v);
        addE(u, t); addE(t, v); t++;
    }
    dfs(1, 0);
    initlca(t);
    T.init();
    cal(1, n);
    printf("%lld\n", Ans/2);
}
int main() {
    int t=1;
//    scanf("%d", &t);
//    init();
    REQ(i,t) {
        fmain(i);
    }
    return 0;
}