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 rd(x) x=read()

#define N 200005
#define int long long

using namespace std;

int n,k;
vector<int>e[N];
int vis[N],mn,rt;
int s[N],dep[N],p[N][21],faa[N],f[21][N];
int b[N],c[N],w[N],g[N],suf[N];

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();if(ch==-1)return 0;}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

inline void addEdge(int u,int v){e[u].push_back(v),e[v].push_back(u);}
void dfs(int u,int fa){s[u]=1;for(int v:e[u])if(v!=fa&&!vis[v])dfs(v,u),s[u]+=s[v];}
void dfss(int u,int fa){dep[u]=dep[fa]+1,p[u][0]=fa;for(int i=1;(1<<i)<=dep[u];i++)p[u][i]=p[p[u][i-1]][i-1];for(int v:e[u])if(v!=fa)dfss(v,u);}
void dfsss(int u,int fa,int r){for(int v:e[u])if(v!=fa&&!vis[v])f[r][v]=f[r][u]+1,dfsss(v,u,r);}
void getroot(int u,int fa)
{
	int ans=k-s[u];
	for(int v:e[u])if(v!=fa&&!vis[v])getroot(v,u),ans=max(ans,s[v]);
	if(ans<mn)mn=ans,rt=u;
}
void dfssss(int u,int fa){dfs(u,0),mn=k=s[u],getroot(u,0);vis[u=rt]=1,g[u]=g[faa[u]=fa]+1,dfsss(u,0,g[u]);for(int v:e[u])if(!vis[v])dfssss(v,u);}

int lca(int u,int v)
{
	if(dep[u]>dep[v])swap(u,v);for(int i=20;i>=0;i--)if(dep[u]<=dep[v]-(1<<i))v=p[v][i];
	if(u==v)return u;for(int i=20;i>=0;i--)if(p[u][i]!=p[v][i])u=p[u][i],v=p[v][i];return p[u][0];
}
inline int dis(int u,int v){return dep[u]+dep[v]-2*dep[lca(u,v)];}
inline void ins(int u,int x){for(int i=u,j=g[u];i;i=faa[i],j--){if(j>1)w[i]+=x*f[j-1][u];b[i]+=x*f[j][u],c[i]+=x;}}
inline int query(int u){int ans=b[u];for(int i=u,j=faa[u],l=g[u]-1;j;i=j,j=faa[j],l--)ans+=(c[j]-c[i])*f[l][u]+b[j]-w[i];return ans;}
int getanc(int u,int d){for(int i=20;i>=0;i--)if(d>=(1<<i))d-=(1<<i),u=p[u][i];return u;}
int getcenter(int u,int v,int d){int t=lca(u,v);if(dep[u]-dep[t]>=d)return getanc(u,d);return getanc(v,dep[v]-dep[t]-(d-=dep[u]-dep[t]));}
struct C{int u,r;}a[N];C add(C x,C y){int d=dis(x.u,y.u);if(y.r+d<=x.r)return x;if(x.r+d<=y.r)return y;return C{getcenter(x.u,y.u,(x.r+d+y.r)/2-x.r),(x.r+d+y.r)/2};}
inline bool check1(int i,int j){return a[i].r+dis(a[i].u,a[j].u)<=a[j].r;}inline bool check2(int i,int j){return a[i].r+dis(a[i].u,a[j].u)<a[j].r;}

int ans;
void solve(int l,int r)
{
	if(l==r)return ;int mid=(l+r)>>1;
	a[mid]=C{mid,0};for(int i=mid-1;i>=l;i--)a[i]=add(a[i+1],C{i,0});
	a[mid+1]=C{mid+1,0};for(int i=mid+2;i<=r;i++)a[i]=add(a[i-1],C{i,0});
	int L=mid,R=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(R<=r&&!check1(i,R))ins(a[R++].u,1);
		while(L<r&&check2(L+1,i))ins(a[++L].u,-1);
		ans+=suf[R]+1ll*(L-mid)*a[i].r+(suf[L+1]-suf[R]+1ll*(R-L-1)*a[i].r+query(a[i].u))/2;
	}
	while(L+1<R)ins(a[++L].u,-1);solve(l,mid),solve(mid+1,r);
}

signed main()
{
	rd(n);
	for(int i=1,u,v;i<n;i++)rd(u),rd(v),addEdge(u,i+n),addEdge(i+n,v);
	dfss(1,0),dfssss(1,0),solve(1,n),cout<<ans<<endl;
	

    return 0;
}