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);
        	ll pre=ans;
     /*   	if(flag&&l==1&&r==n){
        		for(int i=1;i<=2*n-1;++i)if(c[i]||toc[i]||dis[i]||todis[i]){
        			printf("%d %d %lld %lld\n",c[i],toc[i],dis[i],todis[i]);
        			puts("fuck");
				}
			}*/
        	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]);
       /* 		if(flag&&(l==1&&r==n)){
        			printf("(%d %d %lld %lld)\n",L,R,ans-pre,t.query(tmp.O));
				}*/
        	}
        	for(int i=L+1;i<R;++i)t.update(a[i].O,-1);
      /*  	if(flag&&l==1&&r==n){
        		printf("%lld\n",ans-pre);
        	}*/
        }
        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);
        }