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
using namespace std;
int n,m,head[200010],o=0,sz[200010],dep[200010],fa[200010],son[200010],top[200010],id[200010],x=0,re[200010];
ll tr[200010],tr2[200010],sum[100010],ans=0;
struct edge{
	int to,link;
}e[400010];
struct cir{
	int p,r;
	cir(int _p=0,int _r=0){
		p=_p,r=_r;
	}
}a[100010];
void add_edge(int u,int v){
	e[++o]=(edge){v,head[u]},head[u]=o;
	e[++o]=(edge){u,head[v]},head[v]=o;
}
void dfs(int u,int pre){
	sz[u]=1,fa[u]=pre,dep[u]=dep[pre]+1;
	for(int i=head[u];i;i=e[i].link) if(e[i].to!=pre){
		dfs(e[i].to,u);
		if(sz[son[u]]<sz[e[i].to]) son[u]=e[i].to;
		sz[u]+=sz[e[i].to];
	}
}
void dfs2(int u,int tpf){
	top[u]=tpf,id[u]=++x,re[x]=u;
	if(son[u]) dfs2(son[u],tpf);
	for(int i=head[u];i;i=e[i].link) if(e[i].to!=fa[u]&&e[i].to!=son[u]){
		dfs2(e[i].to,e[i].to);
	}
}
int lca(int u,int v){
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		u=fa[top[u]];
	}
	return dep[u]>dep[v]?v:u;
}
int dis(int u,int v){
	return dep[u]+dep[v]-2*dep[lca(u,v)];
}
void add(int x,int c){
	for(int i=x;i<=m;i+=(i&-i)) tr[i]+=c,tr2[i]+=c*(x-1ll);
}
ll qry(int x){
	ll res=0;
	for(int i=x;i;i-=(i&-i)) res+=tr[i]*x-tr2[i];
	return res;
}
void add(int l,int r,int c){
	add(l,c),add(r+1,-c);
}
void add_cl(int u,int c){
	while(u){
		add(id[top[u]],id[u],c);
		u=fa[top[u]];
	}
}
ll qry_cl(int u){
	ll res=0;
	while(u){
		res+=qry(id[u])-qry(id[top[u]]-1);
		u=fa[top[u]];
	}
	return res;
}
int go(int u,int v,int k){
	int w=lca(u,v);
	if(dep[u]-dep[w]>=k){
		while(dep[u]-dep[top[u]]+1<=k){
			k-=dep[u]-dep[top[u]]+1;
			u=fa[top[u]];
		}
		return re[id[u]-k];
	}
	else return go(v,u,dep[u]+dep[v]-2*dep[w]-k);
}
cir operator +(cir u,cir v){
	int d=dis(u.p,v.p),R=(u.r+v.r+d)/2;
	if(u.r>v.r) swap(u,v);
	if(d+u.r<=v.r) return v;
	return cir(go(u.p,v.p,R-u.r),R);
}
void work(int l,int r){
	if(l==r) return;
	int mid=(l+r)>>1,L=mid,R=mid+1;
	work(l,mid),work(mid+1,r);
	cir nw(mid,0);
	sum[mid]=sum[mid+1]=0,a[mid+1]=cir(mid+1,0);
	for(int i=mid+2;i<=r;i++) a[i]=a[i-1]+cir(i,0),sum[i]=sum[i-1]+a[i].r;
	ll cnt=0;
	for(int i=mid;i>=l;i--){
		nw=nw+cir(i,0);
		while(L<r&&a[L+1].r<=nw.r-dis(nw.p,a[L+1].p)) add_cl(a[++L].p,-1),cnt-=dep[a[L].p];
		while(R<=r&&a[R].r-dis(nw.p,a[R].p)<=nw.r) cnt+=(dep[a[R].p]),add_cl(a[R++].p,1);
		ans+=1ll*(R-L-1)*dep[nw.p]+cnt-2ll*qry_cl(nw.p)+2ll*(L-mid)*nw.r+2ll*(sum[r]-sum[R-1])+1ll*(R-L-1)*nw.r+(sum[R-1]-sum[L]);
	}
	for(int i=L+1;i<R;i++) add_cl(a[i].p,-1);
}
int main(){
	scanf("%d",&n),m=n;
	for(int i=1,u,v;i<n;i++) scanf("%d%d",&u,&v),++m,add_edge(u,m),add_edge(v,m);
	dfs(1,0),dfs2(1,1);
	work(1,n);
	printf("%lld\n",ans/2);
}