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>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define poly vector<ll>
#define For(i,l,r) for(int i=(int)(l);i<=(int)(r);i++)
#define Rep(i,r,l) for(int i=(int)(r);i>=(int)(l);i--)
#define pb push_back
inline ll read(){
	ll x=0; char ch=getchar(); bool d=1;
	for(;!isdigit(ch);ch=getchar()) if(ch=='-') d=0;
	for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
	return d?x:-x;
}
inline ull rnd(){
	return ((ull)rand()<<30^rand())<<4|rand()%4;
}
const int N=2e5+5;
int fa[20][N],alb[N],zson[N],cson[N];
int dep[N],size[N],mx[N],top[N],TOP[N];
poly v[N],up[N],dw[N];
void dfs(int u){
	dep[u]=dep[fa[0][u]]+1;
	size[u]=1; mx[u]=dep[u];
	for(auto k:v[u]){
		if(k==fa[0][u]) continue;
		fa[0][k]=u; dfs(k);
		size[u]+=size[k]; mx[u]=max(mx[u],mx[k]);
		if(!zson[u]||size[k]>size[zson[u]]) zson[u]=k;
		if(!cson[u]||mx[k]>mx[cson[u]]) cson[u]=k;
	}
}
void dfs1(int u,int t){
	top[u]=t;
	if(zson[u]) dfs1(zson[u],t);
	for(auto k:v[u]){
		if(k==fa[0][u]||k==zson[u]) continue;
		dfs1(k,k);
	}
}
void dfs2(int u,int t){
	TOP[u]=t;
	if(u==t){
		int x=u;
		For(i,0,mx[u]-dep[u]) up[u].pb(x),x=fa[0][x];
		x=u;
		For(i,0,mx[u]-dep[u]) dw[u].pb(x),x=cson[x];
	}
	if(cson[u]) dfs2(cson[u],t);
	for(auto k:v[u]){
		if(k==fa[0][u]||k==cson[u]) continue;
		dfs2(k,k);
	}
}
void init(int n){
	dfs(1); dfs1(1,1); dfs2(1,1);
	For(i,1,18){
		For(j,1,n) fa[i][j]=fa[i-1][fa[i-1][j]];
	}
	For(i,2,n) alb[i]=alb[i>>1]+1;
}
int findk(int u,int k){
	if(k==0) return u;
	u=fa[alb[k]][u]; k-=(1<<alb[k]);
	k-=dep[u]-dep[TOP[u]]; u=TOP[u];
	return k>=0?up[u][k]:dw[u][-k];
}
int lca(int x,int y){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		x=fa[0][top[x]];
	}
	return dep[x]<dep[y]?x:y;
}
int D(int x,int y){
	return dep[x]+dep[y]-2*dep[lca(x,y)];
}
int walk(int x,int y,int k){
	int t=lca(x,y);
	if(dep[x]-dep[t]>=k) return findk(x,k);
	return findk(y,dep[x]+dep[y]-2*dep[t]-k);
}
bool in(pii x,pii y){
	return x.se+D(x.fi,y.fi)<=y.se;
}
pii merge(pii x,pii y){
	if(x.se>y.se) swap(x,y);
	int dis=D(x.fi,y.fi);
	if(x.se+dis<y.se) return y;
	int r=(x.se+y.se+dis)/2;
	return mp(walk(x.fi,y.fi,r-x.se),r);
}
struct tree{
	const int inf=0x3f3f3f3f;
	int dep[N],fa[N],sum[N],cnt[N],dis[20][N],rt,mn,size[N];
	bool used[N];
	void dfs(int u,int fa,int n){
		int mx=0; size[u]=1;
		for(auto k:v[u]){
			if(k==fa||used[k]) continue;
			dfs(k,u,n); size[u]+=size[k];
			mx=max(mx,size[k]);
		}
		mx=max(mx,n-size[u]);
		if(mx<mn) mn=mx,rt=u;
	}
	void dfs(int u,int fa,int d,int t){
		dis[d][u]=t;
		for(auto k:v[u]){
			if(k==fa||used[k]) continue;
			dfs(k,u,d,t+1);
		}
	}
	void solve(int u,int n,int d,int pre){
		mn=inf; dfs(u,0,n); used[u=rt]=1;
		dfs(u,0,d,0); dep[u]=d; fa[u]=pre;
		for(auto k:v[u]){
			if(used[k]) continue;
			solve(k,size[k]>size[u]?n-size[u]:size[k],d+1,u);
		}
	}
	ll sum1[N],cnt1[N],sum2[N],cnt2[N];
	void ins(int x,int w){
		// cout<<"sana "<<x<<" "<<w<<" "<<fa[x]<<endl;
		cnt1[x]+=w; int t=x;
		while(fa[x]){
			int y=fa[x],d=dep[y];
			cnt1[y]+=w; sum1[y]+=w*dis[d][t];
			cnt2[x]+=w; sum2[x]+=w*dis[d][t];
			x=fa[x];
		}
	}
	ll find(int x){
		int t=x; ll ans=sum1[x];
		while(fa[x]){
			int y=fa[x],d=dep[y];
			ans+=sum1[y]+cnt1[y]*dis[d][t];
			ans-=sum2[x]+cnt2[x]*dis[d][t];
			x=fa[x];
		}
		return ans;
	}
}T;
ll sum[N],ans;
pii a[N];
void solve(int l,int r){
	if(l==r) return;
	int mid=l+r>>1;
	solve(l,mid); solve(mid+1,r);
	a[mid]=mp(mid,0); a[mid+1]=mp(mid+1,0);
	Rep(i,mid-1,l) a[i]=merge(a[i+1],mp(i,0));
	For(i,mid+2,r) a[i]=merge(a[i-1],mp(i,0));
	sum[mid]=0;
	For(i,mid+1,r) sum[i]=sum[i-1]+a[i].se;
	int L=mid+1,R=mid+1;
	Rep(i,mid,l){
		while(R<=r&&!in(a[i],a[R])) T.ins(a[R].fi,1),R++;
		while(L<R&&in(a[L],a[i])) T.ins(a[L].fi,-1),L++;
		// cout<<"mjn "<<L<<" "<<R<<" "<<T.find(a[i].fi)<<endl;
		ans+=2ll*(sum[r]-sum[R-1]);
		ans+=2ll*a[i].se*(L-mid-1);
		ans+=sum[R-1]-sum[L-1];
		ans+=(ll)a[i].se*(R-L);
		ans+=T.find(a[i].fi);
	}
	For(i,L,R-1) T.ins(a[i].fi,-1);
}
int main(){
	int n=read();
	For(i,1,n-1){
		int x=read(),y=read();
		v[n+i].pb(x); v[x].pb(n+i);
		v[n+i].pb(y); v[y].pb(n+i);
	}
	init(2*n-1); T.solve(1,2*n-1,1,0);
	solve(1,n); cout<<ans/2;
}