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 For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define pii pair<int,int>
#define fi first
#define se second
#define PB push_back
#define ll long long
#define ull unsigned long long
using namespace std;

const int N=200005;
int n;
vector<int> e[N];
int fa[N],dep[N],sz[N];
int dfn[N],ed[N],pos[N],top[N];
void dfs1(int x){
	sz[x]=1;
	for (auto i:e[x])
		if (i!=fa[x]){
			fa[i]=x;
			dep[i]=dep[x]+1;
			dfs1(i);
			sz[x]+=sz[i];
		}
}
void dfs2(int x,int tp){
	dfn[x]=++*dfn;
	pos[*dfn]=x;
	top[x]=tp;
	int k=0;
	for (auto i:e[x])
		if (i!=fa[x]&&sz[i]>sz[k])
			k=i;
	if (k) dfs2(k,tp);
	for (auto i:e[x])
		if (i!=fa[x]&&i!=k)
			dfs2(i,i);
	ed[x]=*dfn; 
}
struct T{
	int dep[N],fa[N],sz[N],vis[N];
	int dis[20][N],rt;
	void dfs(int x,int fa,int n){
		sz[x]=1;
		int mx=0;
		for (auto i:e[x])
			if (i!=fa&&!vis[i]){
				dfs(i,x,n);
				sz[x]+=sz[i];
				mx=max(mx,sz[i]);
			}
		if (sz[x]*2>=n&&mx*2<n) rt=x;
	}
	void dfs2(int x,int fa,int *d){
		d[x]=d[fa]+1;
		for (auto i:e[x])
			if (!vis[i]&&i!=fa) dfs2(i,x,d);
	}
	int solve(int x,int n,int d){
		dfs(x,0,n);
		vis[x=rt]=1; dep[x]=d;
		for (auto i:e[x]) if (!vis[i])
			dfs2(i,x,dis[d]);
		for (auto i:e[x]) if (!vis[i])
			fa[solve(i,sz[i]<sz[x]?sz[i]:n-sz[x],d+1)]=x;
		return x;
	}
	void init(){
		fa[solve(1,2*n-1,1)]=0;
	}
	ll s1[N],n1[N];
	ll s2[N],n2[N];
	void inc(int x,int v){
		n1[x]+=v;
		for (int p=x;fa[x];){
			int y=fa[x],d=dep[fa[x]];
			n1[y]+=v; s1[y]+=dis[d][p]*v;
			n2[x]+=v; s2[x]+=dis[d][p]*v;
			x=y;
		}
	}
	ll query(int x){
		ll ans=s1[x];
		for (int p=x;fa[x];){
			int y=fa[x],d=dep[fa[x]];
			ans+=s1[y]+n1[y]*dis[d][p];
			ans-=s2[x]+n2[x]*dis[d][p];
			x=y;
		}
		return ans;
	}
}T;
int LCA(int x,int y){
	for (;top[x]!=top[y];x=fa[top[x]])
		if (dep[top[x]]<dep[top[y]]) swap(x,y);
	return dep[x]<dep[y]?x:y;
}
int kthfa(int x,int d){
	for (;;)
		if (dep[x]-dep[top[x]]>=d)
			return pos[dfn[x]-d];
		else{
			d-=dep[x]-dep[top[x]]+1;
			x=fa[top[x]];
		}
}
int walk(int x,int y,int stp){
	int L=LCA(x,y);
	if (dep[x]-dep[L]>=stp)
		return kthfa(x,stp);
	return kthfa(y,(dep[y]+dep[x]-2*dep[L])-stp);
}
int dis(int x,int y){
	return dep[x]+dep[y]-2*dep[LCA(x,y)];
}
pii R[N];
ll S[N],ans;
bool in(pii x,pii y){
	return x.se+dis(x.fi,y.fi)<=y.se;
}
pii Merge(pii x,pii y){
	if (x.se>y.se) swap(x,y);
	int d=dis(x.fi,y.fi);
	if (x.se+d<y.se) return y;
	int R=(x.se+y.se+d)/2;
	return pii(walk(x.fi,y.fi,R-x.se),R);
}
void count(int l,int mid,int r){
	R[mid]=pii(mid,0);
	R[mid+1]=pii(mid+1,0);
	Rep(i,mid-1,l) R[i]=Merge(R[i+1],pii(i,0));
	For(i,mid+2,r) R[i]=Merge(R[i-1],pii(i,0));
	S[mid]=0;
	For(i,mid+1,r) S[i]=S[i-1]+R[i].se;
	int pl=mid+1,pr=mid+1;
	Rep(i,mid,l){
		for (;pr<=r&&!in(R[i],R[pr]);++pr) T.inc(R[pr].fi,1);
		for (;pl<pr&&in(R[pl],R[i]);++pl) T.inc(R[pl].fi,-1);
		ans+=2ll*(S[r]-S[pr-1]);//R include L
		ans+=2ll*R[i].se*(pl-mid-1);// L include R
		ans+=1ll*(S[pr-1]-S[pl-1]);
		ans+=1ll*R[i].se*(pr-pl);
		ans+=T.query(R[i].fi);
	}
	For(i,pl,pr-1) T.inc(R[i].fi,-1);
}
void solve(int l,int r){
	if (l==r) return;
	int mid=(l+r)/2;
	solve(l,mid);
	solve(mid+1,r);
	count(l,mid,r);
}
int main(){
	scanf("%d",&n);
	For(i,1,n-1){
		int x,y; 
		scanf("%d%d",&x,&y);
		e[n+i].PB(x); e[x].PB(n+i);
		e[n+i].PB(y); e[y].PB(n+i);
	}
	dfs1(1);
	dfs2(1,1);
	T.init();
	solve(1,n);
	cout<<ans/2<<endl;
}