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 N 200010
#define int long long
using namespace std;
int n,m,size[N],dp[N][21],head[N],son[N],id[N],ek[N],tr[N*4],pd[N*4],top[N],fa[N],tot,dep[N],fuckljx;
struct edge{
	int to,next;
}dat[N*2];
void add_edge(int x,int y){
	dat[++tot].next=head[x];
	dat[tot].to=y;
	head[x]=tot;
}
void dfs1(int x,int f){
	dep[x]=dep[f]+1;
	fa[x]=f;
	size[x]=1;
	dp[x][0]=f;
	for(int i=1;i<=20;i++)dp[x][i]=dp[dp[x][i-1]][i-1];
	for(int i=head[x];i;i=dat[i].next){
		int t=dat[i].to;
		if(t==f)continue;
		dfs1(t,x);
		size[x]+=size[t];
		if(size[t]>size[son[x]])son[x]=t;
	}
}
void dfs2(int x,int h){
	top[x]=h;
	id[x]=++fuckljx;
	ek[fuckljx]=x;
	if(son[x])dfs2(son[x],h);
	for(int i=head[x];i;i=dat[i].next){
		int t=dat[i].to;
		if(t==son[x]||t==fa[x])continue;
		dfs2(t,t);
	} 
}
void update(int x){
	tr[x]=tr[x*2]+tr[x*2+1];
}
void push(int x,int l,int r){
	if(pd[x]){
		int mid=(l+r)/2;
		tr[x*2]+=(mid-l+1)*pd[x];
		tr[x*2+1]+=(r-mid)*pd[x];
		pd[x*2]+=pd[x];
		pd[x*2+1]+=pd[x];
		pd[x]=0;
	}
}
int query(int x,int l,int r,int s,int t){
	if(l>t||r<s)return 0;
	if(s<=l&&r<=t)return tr[x];
	int mid=(l+r)/2;
	push(x,l,r);
	return query(x*2,l,mid,s,t)+query(x*2+1,mid+1,r,s,t);
}
void change(int x,int l,int r,int s,int t,int val){
	if(l>t||r<s)return;
	if(s<=l&&r<=t){
		tr[x]+=val*(r-l+1);
		pd[x]+=val;
		return;
	}
	push(x,l,r);
	int mid=(l+r)/2;
	change(x*2,l,mid,s,t,val);
	change(x*2+1,mid+1,r,s,t,val);
	update(x);
}
void add(int x,int val){
//	cout<<"add "<<x<<' '<<val<<endl;
	while(x){
		change(1,1,m,id[top[x]],id[x],val);
		x=fa[top[x]];
	}
} 
int go(int x){
	long long sum=0;
	int xx=x;
	while(x){
		sum+=query(1,1,m,id[top[x]],id[x]);
		x=fa[top[x]];
	}
//	cout<<"go "<<xx<<' '<<dep[xx]<<' '<<sum<<endl;
	return sum;
}
#define fx top[x]
#define fy top[y]
int lca(int x,int y){
	while(fx!=fy){
		if(dep[fx]<dep[fy])swap(x,y);
		x=fa[fx];
	}
	if(dep[x]<dep[y])swap(x,y);
	return y;
}
int dis(int x,int y){
	return dep[x]+dep[y]-2*dep[lca(x,y)];
}
int up(int x,int k){
	for(int i=20;i>=0;i--){
		if(k>=(1<<i))x=dp[x][i],k-=(1<<i);
	}
	return x;
}
int getmid(int x,int y){
	int LCA=lca(x,y);
	int DIS=dep[x]+dep[y]-2*dep[lca(x,y)];
	if(dep[x]<dep[y])swap(x,y);
//	cout<<"mid "<<x<<' '<<y<<' '<<DIS<<' '<<up(x,DIS/2)<<endl;
	return up(x,DIS/2);
} 
int to(int x,int y,int num){
	int LCA=lca(x,y);
	if(dep[x]-dep[LCA]>=num)return up(x,num);
	num-=(dep[x]-dep[LCA]);
	num=(dep[y]-dep[LCA])-num;
	return up(y,num);
}
struct fuck{
	int r,mid;
}cir[N];
fuck operator + (fuck a,fuck b){
	if(a.r<b.r)swap(a,b);
	if(dis(b.mid,a.mid)+b.r<=a.r)return (fuck){a.r,a.mid};
	int R=(a.r+b.r+dis(a.mid,b.mid))/2;
	int mid=to(b.mid,a.mid,R-b.r);
//	cout<<"fuclsasdasdasd "<<a.mid<<' '<<b.mid<<' '<<R-b.r<<' '<<mid<<endl;
	return (fuck){(a.r+b.r+dis(a.mid,b.mid))/2,mid};
}
long long sum[N],ans;
void solve(int l,int r){
	if(l==r)return;
	int mid=(l+r)/2;
	solve(l,mid),solve(mid+1,r);
	cir[mid]=(fuck){0,mid},cir[mid+1]=(fuck){0,mid+1},sum[mid]=sum[mid+1]=0;
	for(int i=mid-1;i>=l;i--)cir[i]=cir[i+1]+(fuck){0,i},sum[i]=sum[i+1]+cir[i].r;
	for(int i=mid+2;i<=r;i++)cir[i]=cir[i-1]+(fuck){0,i},sum[i]=sum[i-1]+cir[i].r;
	int nowl=mid+1,nowr=mid;
	long long cnt=0;
	for(int i=mid;i>=l;i--){
		while(nowr+1<=r&&cir[nowr+1].r<dis(cir[i].mid,cir[nowr+1].mid)+cir[i].r)cnt+=dep[cir[++nowr].mid],add(cir[nowr].mid,1);
//		cout<<"fuckljx "<<nowr+1<<' '<<cir[nowr+1].r<<' '<<dis(cir[i].mid,cir[nowr+1].mid)<<' '<<cir[i].r<<endl;
		while(nowl<=nowr&&cir[i].r>=dis(cir[i].mid,cir[nowl].mid)+cir[nowl].r)cnt-=dep[cir[nowl].mid],add(cir[nowl++].mid,-1);
//		cout<<"check "<<nowl<<' '<<nowr<<endl;
//		cout<<"fuck "<<cir[i].r<<' '<<(nowl-(mid+1))<<' '<<(sum[r]-sum[nowr])<<endl;
		ans+=2ll*cir[i].r*(nowl-(mid+1))+2ll*(sum[r]-sum[nowr]);
//		cout<<"fuck "<<cir[i].r<<' '<<nowr-nowl+1<<' '<<sum[nowr]-sum[nowl-1]<<' '<<cnt<<' '<<dep[i]*(nowr-nowl+1)<<' '<<go(i)<<endl; 
		ans+=1ll*cir[i].r*(nowr-nowl+1)+1ll*(sum[nowr]-sum[nowl-1])+0ll+cnt+1ll*dep[cir[i].mid]*(nowr-nowl+1)-2ll*go(cir[i].mid);
//		cout<<"ans "<<ans<<endl;
	}
	while(nowl<=nowr)add(cir[nowl++].mid,-1);
//	cout<<l<<' '<<r<<' '<<ans<<endl;
}
#undef int
int main(){
	cin>>n;
	m=n;
	for(int i=1;i<n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		m++;
		add_edge(x,m);
		add_edge(m,x);
		add_edge(y,m);
		add_edge(m,y);
	}
	dfs1(1,0);
	dfs2(1,1);
	solve(1,n);
	cout<<ans/2;
}