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;
const int N=200001;
int n,tag,pre[N],q[N],sz[N],col[N],pr[N];
int num[N],fa[N][19],dep[N],rad[N],cen[N];ll ds[N],dsf[N],sum[N],ans;
vector<int>e[N],dis[N];
void dfs(int p){
	for(int i=0;fa[p][i];++i)
		fa[p][i+1]=fa[fa[p][i]][i];
	for(int i=0,sz=e[p].size();i<sz;++i){
		int to=e[p][i];
		if(to!=fa[p][0])
			dep[to]=dep[p]+1,fa[to][0]=p,dfs(to);
	}
}
int kthp(int u,int k){
	for(int i=0;k;k>>=1,++i)
		if(k&1) u=fa[u][i];
	return u;
}
int lca(int u,int v){
	if(dep[u]<dep[v]) swap(u,v);
	u=kthp(u,dep[u]-dep[v]);
	if(u==v) return u;
	for(int i=18;i>=0;--i)
		if(fa[u][i]!=fa[v][i])
			u=fa[u][i],v=fa[v][i];
	return fa[u][0];
}
int dist(int u,int v){
	return dep[u]+dep[v]-2*dep[lca(u,v)];
}
int solve(int p){
	++tag;int l,r;
	pre[q[l=r=1]=p]=0;
	while(l<=r){
		int x=q[l++];sz[x]=1;
		for(int i=e[x].size()-1;i>=0;--i){
			int to=e[x][i];
			if(to!=p&&col[to]==col[p])
				pre[to]=x,col[q[++r]=to]=tag;
		}
	}
	for(int i=r;i>1;--i)
		sz[pre[q[i]]]+=sz[q[i]];
	int mv=1e9,mp=0;
	for(int i=1;i<=r;++i){
		int x=q[i],mx=r-sz[x];
		for(int j=e[x].size()-1;j>=0;--j){
			int to=e[x][j];
			if(col[to]==tag&&pre[to]==x)
				mx=max(mx,sz[to]);
		}
		if(mx<mv) mv=mx,mp=x;
	}
	swap(col[p],col[mp]),p=mp;
	pre[q[l=r=1]=p]=sz[p]=0;
	while(l<=r){
		int x=q[l++];
		for(int i=e[x].size()-1;i>=0;--i){
			int to=e[x][i];
			if(to!=pre[x]&&col[to]==tag)
				pre[q[++r]=to]=x,sz[to]=sz[x]+1;
		}
	}
	for(int i=1;i<=r;++i)
		dis[q[i]].push_back(sz[q[i]]);
	int tg=tag;
	for(int i=e[p].size()-1;i>=0;--i)
		if(col[e[p][i]]==tg)
			pr[solve(e[p][i])]=p;
	return p;
}
void modify(int p,int v){
	for(int i=p,u=dis[p].size()-1;i;i=pr[i],--u){
		num[i]+=v,ds[i]+=v*dis[p][u];
		if(pr[i]) dsf[i]+=v*dis[p][u-1];
	}
}
ll qry(int p){
	ll ret=ds[p];
	for(int i=p,f=pr[p],u=dis[p].size()-2;f;i=pr[i],f=pr[f],--u)
		ret+=ll(num[f]-num[i])*dis[p][u]+ds[f]-dsf[i];
	return ret;
}
int find(int u,int v,int d){
	int p=lca(u,v);
	if(dep[u]-dep[p]>=d)
		return kthp(u,d);
	return kthp(v,dep[v]-dep[p]-(d-(dep[u]-dep[p])));
}
void solve(int l,int r){
	if(l==r) return;
	int mid=l+r>>1;
	rad[mid]=0,cen[mid]=mid;
	for(int i=mid-1;i>=l;--i){
		int d=dist(i,cen[i+1]);
		if(d<=rad[i+1])
			rad[i]=rad[i+1],cen[i]=cen[i+1];
		else rad[i]=(rad[i+1]+d)/2,cen[i]=find(i,cen[i+1],rad[i]);
	}
	rad[mid+1]=sum[mid]=sum[mid+1]=0,cen[mid+1]=mid+1;
	for(int i=mid+2;i<=r;++i){
		int d=dist(i,cen[i-1]);
		if(d<=rad[i-1])
			rad[i]=rad[i-1],cen[i]=cen[i-1];
		else rad[i]=(rad[i-1]+d)/2,cen[i]=find(i,cen[i-1],rad[i]);
		sum[i]=sum[i-1]+rad[i];
	}
	int s=mid+1,t=mid;
	for(int i=mid;i>=l;--i){
		for(;s<=r&&dist(cen[i],cen[s])+rad[s]<=rad[i];++s) modify(cen[s],-1);
		for(;t<s-1||(t<r&&dist(cen[i],cen[t+1])+rad[i]>rad[t+1]);++t) modify(cen[t+1],1);
		ans+=rad[i]*2*(s-mid-1ll)+2*(sum[r]-sum[t]);
		ans+=(t-s+1ll)*rad[i]+sum[t]-sum[s-1]+qry(cen[i]);
	}
	for(;s<=t;++s) modify(cen[s],-1);
	solve(l,mid),solve(mid+1,r);
}
int main(){
	scanf("%d",&n);
	for(int i=1,u,v;i<n;++i){
		scanf("%d%d",&u,&v);
		e[i+n].push_back(u),e[u].push_back(i+n);
		e[i+n].push_back(v),e[v].push_back(i+n);
	}
	dfs(1),solve(1);
	solve(1,n);
	printf("%I64d",ans/2);
	return 0;
}