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:
#define DEBUG 0

#include <bits/stdc++.h>
using namespace std;

#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}

// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
    public:
        template<typename T>
        _Debug& operator,(T val) {
            cout << val << endl;
            return *this;
        }
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif

// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back

// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;

// ---------- END OF TEMPLATE ----------

vi adjList[200000];
int parent[200000][18],depth[200000];
int doDFS(int u,int p,int d) {
    int i;
    parent[u][0] = p,depth[u] = d;
    for (i = 0; i < adjList[u].size(); i++) {
        int v = adjList[u][i];
        if (v != p) doDFS(v,u,d+1);
    }
    return 0;
}
int logn;
int lca(int u,int v) {
    if (depth[u] < depth[v]) swap(u,v);
    int i;
    for (i = logn-1; i >= 0; i--) {
        if ((parent[u][i] != -1) && (depth[parent[u][i]] >= depth[v])) u = parent[u][i];
    }
    if (u == v) return u;
    for (i = logn-1; i >= 0; i--) {
        if (parent[u][i] != parent[v][i]) u = parent[u][i],v = parent[v][i];
    }
    return parent[u][0];
}
int midpoint(int u,int v,int d) {
    int i;
    if (depth[u] < depth[v]) swap(u,v);
    for (i = 0; i < logn; i++) {
        if ((d/2) & (1 << i)) u = parent[u][i];
    }
    return u;
}
int dist(int u,int v) {
    return depth[u]+depth[v]-2*depth[lca(u,v)];
}
int visited[200000],size[200000],parent2[200000];
vi adjList2[200000];
int layer[200000],depth2[18][200000],sub[18][200000];
int doDFS2(int u,int p) {
    int i;
    size[u] = 1;
    for (i = 0; i < adjList[u].size(); i++) {
        int v = adjList[u][i];
        if (!visited[v] && (v != p)) size[u] += doDFS2(v,u);
    }
    return size[u];
}
int centroid(int u) {
    int i,p = -1,r = u;
    doDFS2(u,-1);
    while (1) {
        int h = -1;
        for (i = 0; i < adjList[u].size(); i++) {
            int v = adjList[u][i];
            if (!visited[v] && (v != p) && ((h == -1) || (size[v] > size[h]))) h = v;
        }
        if (((h == -1) || (size[h] <= size[r]/2)) && (size[r]-size[u] <= size[r]/2)) break;
        else p = u,u = h;
    }
    return u;
}
int doDFS3(int u,int p,int d,int l,int s) {
    int i;
    depth2[l][u] = d,sub[l][u] = s;
    for (i = 0; i < adjList[u].size(); i++) {
        int v = adjList[u][i];
        if (!visited[v] && (v != p)) doDFS3(v,u,d+1,l,s);
    }
    return 0;
}
int decompose(int u,int l) {
    int i,x = 0;
    u = centroid(u);
    visited[u] = 1,layer[u] = l;
    for (i = 0; i < adjList[u].size(); i++) {
        int v = adjList[u][i];
        if (!visited[v]) {
            doDFS3(v,u,1,l,x++);
            v = decompose(v,l+1);
            parent2[v] = u,adjList2[u].pb(v);
        }
    }
    return u;
}

LLI ans = 0;
vector<pair<pii,int> > data[200000];
vector<vector<pair<pii,int> > > data2[200000];
bool comp1(pair<pii,int> a,pair<pii,int> b) {
    return a.first.first+a.first.second < b.first.first+b.first.second;
}
bool comp2(pair<pii,int> a,pair<pii,int> b) {
    return a.first.first-a.first.second < b.first.first-b.first.second;
}
vi vv;
vpii vv2;
int findAns(int l,int r) {
    if (l == r) return 0;
    int i,m = (l+r) / 2;
    pii diam = mp(m,m);
    int d = 0;
    LLI sum1 = 0,sum2 = 0;
    for (i = m; i >= l; i--) {
        int d1 = dist(diam.first,i),d2 = dist(diam.second,i);
        if (max(d1,d2) > d) {
            if (d1 > d2) diam.second = i,d = d1;
            else diam.first = i,d = d2;
        }
        int u = midpoint(diam.first,diam.second,d),r = d/2,o = u;
        sum1 += r;
        data[u].pb(mp(mp(r,0),1)),vv.pb(u);
        while (parent2[u] != -1) {
            int p = parent2[u],s = sub[layer[p]][u],d = depth2[layer[p]][o];
            data[p].pb(mp(mp(r,-d),1)),vv.pb(p);
            data2[p][s].pb(mp(mp(r,-d),1)),vv2.pb(mp(p,s));
            u = p;
        }
    }
    diam = mp(m+1,m+1),d = 0;
    for (i = m+1; i <= r; i++) {
        int d1 = dist(diam.first,i),d2 = dist(diam.second,i);
        if (max(d1,d2) > d) {
            if (d1 > d2) diam.second = i,d = d1;
            else diam.first = i,d = d2;
        }
        int u = midpoint(diam.first,diam.second,d),r = d/2,o = u;
        sum2 += r;
        data[u].pb(mp(mp(r,0),2)),vv.pb(u);
        while (parent2[u] != -1) {
            int p = parent2[u],s = sub[layer[p]][u],d = depth2[layer[p]][o];
            data[p].pb(mp(mp(r,d),2)),vv.pb(p);
            data2[p][s].pb(mp(mp(r,d),2)),vv2.pb(mp(p,s));
            u = p;
        }
    }
    int j;
    ans += 2*(sum1*(r-m)+sum2*(m-l+1));
    for (i = 0; i < vv.size(); i++) {
        vector<pair<pii,int> > &v = data[vv[i]];
        sort(v.begin(),v.end(),comp1);
        LLI s1 = 0,c1 = 0,s2 = 0,c2 = 0;
        for (j = 0; j < v.size(); j++) {
            if (v[j].second == 2) {
                ans += c1*(v[j].first.first+v[j].first.second)-s1;
                c2++,s2 += v[j].first.first+v[j].first.second;
            }
            else {
                ans += c2*(v[j].first.first+v[j].first.second)-s2;
                c1++,s1 += v[j].first.first+v[j].first.second;
            }
        }
        sort(v.begin(),v.end(),comp2);
        s1 = c1 = s2 = c2 = 0;
        for (j = 0; j < v.size(); j++) {
            if (v[j].second == 2) {
                ans += c1*(v[j].first.first-v[j].first.second)-s1;
                c2++,s2 += v[j].first.first-v[j].first.second;
            }
            else {
                ans += c2*(v[j].first.first-v[j].first.second)-s2;
                c1++,s1 += v[j].first.first-v[j].first.second;
            }
        }
        v.clear();
    }
    for (i = 0; i < vv2.size(); i++) {
        vector<pair<pii,int> > &v = data2[vv2[i].first][vv2[i].second];
        sort(v.begin(),v.end(),comp1);
        LLI s1 = 0,c1 = 0,s2 = 0,c2 = 0;
        for (j = 0; j < v.size(); j++) {
            if (v[j].second == 2) {
                ans -= c1*(v[j].first.first+v[j].first.second)-s1;
                c2++,s2 += v[j].first.first+v[j].first.second;
            }
            else {
                ans -= c2*(v[j].first.first+v[j].first.second)-s2;
                c1++,s1 += v[j].first.first+v[j].first.second;
            }
        }
        sort(v.begin(),v.end(),comp2);
        s1 = c1 = s2 = c2 = 0;
        for (j = 0; j < v.size(); j++) {
            if (v[j].second == 2) {
                ans -= c1*(v[j].first.first-v[j].first.second)-s1;
                c2++,s2 += v[j].first.first-v[j].first.second;
            }
            else {
                ans -= c2*(v[j].first.first-v[j].first.second)-s2;
                c1++,s1 += v[j].first.first-v[j].first.second;
            }
        }
        v.clear();
    }
    vv.clear(),vv2.clear();
    findAns(l,m),findAns(m+1,r);
    return 0;
}
int main() {
    int i,j;
    int n,u,v;
    scanf("%d",&n);
    for (i = 0; i < n-1; i++) {
        scanf("%d %d",&u,&v);
        u--,v--;
        adjList[u].pb(i+n);
        adjList[i+n].pb(u);
        adjList[v].pb(i+n);
        adjList[i+n].pb(v);
    }
    n = 2*n-1;
    doDFS(0,-1,0);
    for (i = 1; (1 << i) < n; i++) {
        for (j = 0; j < n; j++) {
            if (parent[j][i-1] != -1) parent[j][i] = parent[parent[j][i-1]][i-1];
            else parent[j][i] = -1;
        }
    }
    logn = i;
    parent2[decompose(0,0)] = -1;
    for (i = 0; i < n; i++) data2[i].resize(adjList[i].size());
    findAns(0,(n-1)/2);
    printf("%lld\n",ans/4);

    return 0;
}