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 O first
#define R second
using namespace std;const int N=4e5+7;typedef long long ll;typedef pair<int,int>pa;
struct data{int to,next;}e[N<<1];int head[N],fa[N][20],p[N],c[N],toc[N],n,m,i,j,k,cnt,vis[N],root,sum,f[N],d[N],size[N];ll ans,dis[N],todis[N],Sum[N];pa a[N];
void ins(int u,int v){e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;}
void insert(int u,int v){ins(u,v);ins(v,u);}
struct Tree{
	void getroot(int x,int fa){
		size[x]=1;f[x]=0;
		for(int i=head[x];i;i=e[i].next)if(e[i].to!=fa&&!vis[e[i].to])
			getroot(e[i].to,x),size[x]+=size[e[i].to],f[x]=max(f[x],size[e[i].to]);
		f[x]=max(f[x],sum-size[x]);if(f[root]>f[x])root=x;
	}
	void work(int x){vis[x]=1;for(int i=head[x];i;i=e[i].next)if(!vis[e[i].to])sum=size[e[i].to],root=0,getroot(e[i].to,x),p[root]=x,work(root);}
	void update(int x,int val){for(c[k=x]+=val,i=p[x];i;x=i,i=p[i])c[i]+=val,j=query(i,k),dis[i]+=j*val,todis[x]+=j*val,toc[x]+=val;}
	ll query(int x){ll res=dis[x];k=x;for(i=p[x];i;x=i,i=p[i])res+=(c[i]-toc[x])*query(k,i)+(dis[i]-todis[x]);return res;}
	void dfs(int x){
		for(int i=1;(1<<i)<=d[x];++i)fa[x][i]=fa[fa[x][i-1]][i-1];
		for(int i=head[x];i;i=e[i].next)if(e[i].to!=fa[x][0])d[e[i].to]=d[x]+1,fa[e[i].to][0]=x,dfs(e[i].to);
	}
	int go(int x,int k){for(int i=19;i>=0;--i)if(k>>i&1)x=fa[x][i];return x;}
	int lca(int x,int y){
		if(d[x]<d[y])swap(x,y);x=go(x,d[x]-d[y]);
		for(int i=19;i>=0;--i)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
		return x==y?x:fa[x][0];
	}
	ll query(int x,int y){return d[x]+d[y]-2*d[lca(x,y)];}
	void init(){f[0]=N;dfs(1);root=0;sum=n+(n-1);getroot(1,0);work(root);}
}t;
pa merge(pa a,pa b){
	if(a.R>b.R)swap(a,b);
	int l=t.query(a.O,b.O),c=t.lca(a.O,b.O);
	pa ret;
	if(l+a.R<=b.R)return b;
	int num=(a.R+b.R+l)/2;ret.R=num;
	if(num-a.R<=d[a.O]-d[c])ret.O=t.go(a.O,num-a.R);else ret.O=t.go(b.O,l-(num-a.R));
	return ret;
}
int flag;
void CDQ(int l,int r){
	if(l==r)return;int mid=l+r>>1;CDQ(l,mid);CDQ(mid+1,r);int L=mid,R=mid+1;a[mid+1]=pa(mid+1,0);Sum[mid+1]=Sum[mid]=0;
	for(int i=mid+2;i<=r;++i)a[i]=merge(a[i-1],pa(i,0)),Sum[i]=Sum[i-1]+a[i].R;pa tmp(mid,0);
	for(int i=mid;i>=l;--i){
		tmp=merge(tmp,pa(i,0));
		while(L<r&&a[L+1].R+t.query(a[L+1].O,tmp.O)<=tmp.R)t.update(a[++L].O,-1);
		while(R<=r&&a[R].R<=tmp.R+t.query(a[R].O,tmp.O))t.update(a[R++].O,1);
		ans+=t.query(tmp.O)+2LL*(L-mid)*tmp.R+2LL*(Sum[r]-Sum[R-1])+1LL*(R-1-L)*tmp.R+(Sum[R-1]-Sum[L]);
	}
	for(int i=L+1;i<R;++i)t.update(a[i].O,-1);
}
int main(){
	for(scanf("%d",&n),i=1;i<n;++i)scanf("%d%d",&j,&k),insert(j,i+n),insert(k,i+n);t.init();
	if(n==1000)flag=1;
	CDQ(1,n);printf("%lld\n",ans/2);
}