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:
//starusc
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
	int x=0,f=1,c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return f==1?x:-x;
}
const int N=2e5+4;
//seg
namespace seg{
	#define lc (p<<1)
	#define rc (p<<1|1)
	#define mid ((l+r)>>1)
	int t[N<<2],len[N<<2],lz[N<<2];
	void build(int p,int l,int r){
		len[p]=r-l+1;
		if(l==r)return;
		build(lc,l,mid);build(rc,mid+1,r);
	}
	inline void pushup(int p){
		t[p]=t[lc]+t[rc];
	}
	inline void pushnow(int p,int v){
		t[p]+=v*len[p];lz[p]+=v;
	}
	inline void pushdown(int p){
		if(!lz[p])return;
		pushnow(lc,lz[p]);pushnow(rc,lz[p]);
		lz[p]=0;
	}
	void modify(int p,int l,int r,int ql,int qr,int v){
		if(ql<=l&&r<=qr){
			pushnow(p,v);
			return;
		}
		pushdown(p);
		if(ql<=mid)modify(lc,l,mid,ql,qr,v);
		if(mid<qr)modify(rc,mid+1,r,ql,qr,v);
		pushup(p);
	}
	int query(int p,int l,int r,int ql,int qr){
		if(ql<=l&&r<=qr)return t[p];
		pushdown(p);
		if(qr<=mid)return query(lc,l,mid,ql,qr);
		if(mid<ql)return query(rc,mid+1,r,ql,qr);
		return query(lc,l,mid,ql,qr)+query(rc,mid+1,r,ql,qr);
	}
	#undef lc
	#undef rc
	#undef mid
}

int n,Q,tim,siz[N],dep[N],son[N],top[N],idx[N],dfn[N],fa[N];
vector<int>e[N];
//slpf
void dfs_1(int x){
	siz[x]=1;
	dep[x]=dep[fa[x]]+1;
	for(auto v:e[x])if(v!=fa[x]){
		fa[v]=x;
		dfs_1(v);
		siz[x]+=siz[v];
		if(siz[v]>siz[son[x]])son[x]=v;
	}
}
void dfs_2(int x,int tp){
	top[x]=tp;
	idx[dfn[x]=++tim]=x;
	if(son[x])dfs_2(son[x],tp);
	for(auto v:e[x])if(v!=fa[x]&&v!=son[x])dfs_2(v,v);
}
inline int findkth(int x,int k){
	if(k>=dep[x])return 1;
	while(dep[x]-dep[top[x]]<k){
		k-=dep[x]-dep[top[x]]+1;
		x=fa[top[x]];
	}
	return idx[dfn[x]-k];
}
inline int getlca(int x,int y){
	while(top[x]!=top[y]){
		if(dep[top[x]]>dep[top[y]])x=fa[top[x]];
		else y=fa[top[y]];
	}
	return dep[x]<dep[y]?x:y;
}
inline int distan(int x,int y){
	return dep[x]+dep[y]-dep[getlca(x,y)]*2;
}
inline int jump(int x,int y,int d){
	int lca=getlca(x,y);
	if(d<=dep[x]-dep[lca])return findkth(x,d);
	else return findkth(y,dep[x]+dep[y]-dep[lca]*2-d);
}
//solve
struct node{
	int x,v;
	node(){}
	node(int xx,int vv):x(xx),v(vv){}
}c[N];
inline bool in(const node &a,const node &b){
	if(a.v>b.v)return 0;
	if(distan(a.x,b.x)+a.v>b.v)return 0;
	return 1;
}
inline node merge(const node &a,const node &b){
	if(in(a,b))return b;
	if(in(b,a))return a;
	return node(jump(a.x,b.x,(distan(a.x,b.x)-a.v+b.v)>>1),(distan(a.x,b.x)+a.v+b.v)>>1);
}
inline void insert(int x,int v){
	while(x){
		seg::modify(1,1,(n<<1)-1,dfn[top[x]],dfn[x],v);
		x=fa[top[x]];
	}
}
inline int query(int x){
	int ret=0;
	while(x){
		ret+=seg::query(1,1,(n<<1)-1,dfn[top[x]],dfn[x]);
		x=fa[top[x]];
	}
	return ret;
}
int ans,p1,p2,s1[N],s2[N];
void solve(int l,int r){
	if(l==r)return;
	int mid=(l+r)>>1;
	solve(l,mid);solve(mid+1,r);
	
	c[mid]=node(mid,0);
	c[mid+1]=node(mid+1,0);
	for(int i=mid-1;i>=l;i--)c[i]=merge(c[i+1],node(i,0));
	for(int i=mid+2;i<=r;i++)c[i]=merge(c[i-1],node(i,0));
	s1[mid]=s2[mid]=0;
	for(int i=mid+1;i<=r;i++){
		s1[i]=s1[i-1]+c[i].v;
		s2[i]=s2[i-1]+dep[c[i].x];
	}
	
	p1=p2=mid;
	for(int i=mid;i>=l;i--){
		while(p1<r&&in(c[p1+1],c[i]))insert(c[++p1].x,-1);
		while(p2<p1||(p2<r&&!in(c[i],c[p2+1])))insert(c[++p2].x,1);
		ans+=c[i].v*(p1-mid)*2+(s1[r]-s1[p2])*2
			+c[i].v*(p2-p1)+s1[p2]-s1[p1]
			+(s2[p2]-s2[p1])+dep[c[i].x]*(p2-p1)-query(c[i].x)*2;
	}
	while(p1<p2)insert(c[++p1].x,-1);
}
signed main(){
	n=read();
	seg::build(1,1,(n<<1)-1);
	for(int i=1,u,v;i<n;i++){
		u=read();v=read();
		e[u].push_back(n+i);e[n+i].push_back(u);
		e[v].push_back(n+i);e[n+i].push_back(v);
	}
	dfs_1(1);dfs_2(1,1);
	solve(1,n);
	cout<<(ans>>1)<<"\n";
	return (0-0);
}