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<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int N=2e5+500;
int to[N<<1],fst[N],nxt[N<<1],n,mm;
void ade(int u,int v){to[++mm]=v,nxt[mm]=fst[u],fst[u]=mm;}
struct HLD
{
	int dep[N],fa[N],tp[N],dfn[N],nid[N],dfs_cnt,son[N],size[N];
	void dfs1(int u,int Fa)
	{
		fa[u]=Fa;size[u]=1;dep[u]=dep[Fa]+1;int mx=0;
		for(int i=fst[u];i;i=nxt[i])
		{
			int v=to[i];if(v==Fa)continue;
			dfs1(v,u);size[u]+=size[v];
			if(size[v]>mx)mx=size[v],son[u]=v;
		}
	}
	void dfs2(int u,int top)
	{
		tp[u]=top;dfn[u]=++dfs_cnt,nid[dfs_cnt]=u;
		if(son[u])dfs2(son[u],top);
		for(int i=fst[u];i;i=nxt[i])
		{
			int v=to[i];if(v==fa[u]||v==son[u])continue;
			dfs2(v,v);
		}
	}
	int lca(int u,int v)
	{
		for(;tp[u]!=tp[v];dep[tp[u]]<dep[tp[v]]?v=fa[tp[v]]:u=fa[tp[u]]);
		return dep[u]<dep[v]?u:v;
	}
	int kthfa(int u,int K)
	{
		while(K>dep[u]-dep[tp[u]])K-=dep[u]-dep[tp[u]]+1,u=fa[tp[u]];
		return nid[dfn[u]-K];
	}
	int go(int u,int v,int K)
	{
		int l=lca(u,v);int d=dep[u]+dep[v]-2*dep[l];
		if(K<=dep[u]-dep[l])return kthfa(u,K);
		else return kthfa(v,d-K);
	}
	int dis(int u,int v){return dep[u]+dep[v]-2*dep[lca(u,v)];}
	void build(){dfs1(1,0),dfs2(1,1);}
}ds1;
struct DFS
{
	vector<pair<int,int> >f[N],g[N];
	int cntf[N],cntg[N],size[N],nn,mxsize,root,vis[N];
	long long sf[N],sg[N];
	void findroot(int u,int fa)
	{
		size[u]=1;int mx=0;
		for(int i=fst[u];i;i=nxt[i])
		{
			int v=to[i];if(v==fa||vis[v])continue;
			findroot(v,u),size[u]+=size[v];
			mx=max(mx,size[v]);
		}
		mx=max(mx,nn-size[u]);
		if(mx<mxsize)root=u,mxsize=mx;
	}
	void dfs1(int u,int anc,int fa,int dep)
	{
		f[u].push_back(make_pair(anc,dep));
		for(int i=fst[u];i;i=nxt[i])
		{
			int v=to[i];if(v==fa||vis[v])continue;
			dfs1(v,anc,u,dep+1);
		}
	}
	void dfs2(int u,int anc,int fa,int dep)
	{
		g[u].push_back(make_pair(anc,dep));
		for(int i=fst[u];i;i=nxt[i])
		{
			int v=to[i];if(v==fa||vis[v])continue;
			dfs2(v,anc,u,dep+1);
		}
	}
	void solve(int u)
	{
//		cout<<u<<endl;
		vis[u]=1;dfs1(u,u,0,0);
		for(int i=fst[u];i;i=nxt[i])
		{
			int v=to[i];if(vis[v])continue;
			nn=size[v],mxsize=1e9,findroot(v,u),dfs2(v,root,u,1),solve(root);
		}
	}
	void build()
	{
		nn=n*2-1,mxsize=1e9;findroot(1,0),solve(root);
	}
	void upd(int u,int w)
	{
		#define IT vector<pair<int,int> >::iterator
		for(IT it=f[u].begin();it!=f[u].end();++it)
			cntf[it->first]+=w,sf[it->first]+=w*it->second;
		for(IT it=g[u].begin();it!=g[u].end();++it)
			cntg[it->first]+=w,sg[it->first]+=w*it->second;
	}
	long long query(int u)
	{
		#define IT vector<pair<int,int> >::iterator
		long long ans=0;
		for(IT it=f[u].begin();it!=f[u].end();++it)
			ans+=1ll*cntf[it->first]*it->second+sf[it->first];
		for(IT it=g[u].begin();it!=g[u].end();++it)
			ans-=1ll*cntg[it->first]*it->second+sg[it->first];
		return ans;
	}
	void print()
	{
		#define IT vector<pair<int,int> >::iterator
		for(int i=1;i<=n;i++)
		{
			printf("%d:\n",i);
			for(IT it=f[i].begin();it!=f[i].end();++it)printf("(%d %d)  ",it->first,it->second);puts("");
			for(IT it=g[i].begin();it!=g[i].end();++it)printf("(%d %d)  ",it->first,it->second);puts("");
			puts("");
		}
	}
}ds2;
struct CIRC
{
	int u,r;
	CIRC(){u=r=0;}
	CIRC(const int &_u,const int &_r){u=_u,r=_r;}
}c[N];
CIRC operator +(const CIRC &a,const CIRC &b)
{
	int d=ds1.dis(a.u,b.u);
	if(a.r+d<=b.r)return b;
	if(b.r+d<=a.r)return a;
	int r=(a.r+b.r+d)>>1;
	return CIRC(ds1.go(a.u,b.u,r-a.r),r);
}
bool operator ==(const CIRC &a,const CIRC &b){return a.u==b.u&&a.r==b.r;}
bool operator !=(const CIRC &a,const CIRC &b){return !(a==b);}
void print(const CIRC &a){printf("(%d %d)\n",a.u,a.r);}
long long ans=0;
void solve(int l,int r)
{
	if(l==r)return;
	int mid=(l+r)>>1;
	solve(l,mid),solve(mid+1,r);
	c[mid+1]=CIRC(mid+1,0);for(int i=mid+2;i<=r;i++)c[i]=c[i-1]+CIRC(i,0);
	c[mid]=CIRC(mid,0);for(int i=mid-1;i>=l;i--)c[i]=c[i+1]+CIRC(i,0);
//	long long tans=ans;
//	cout<<l<<" "<<r<<endl;
//	for(int i=l;i<=mid;i++)print(c[i]);puts("");
//	for(int i=mid+1;i<=r;i++)print(c[i]);puts("");
	long long s1=0,s2=0;
	int cnt1=0,cnt2=0,p=mid,q=l-1;
	while(q<mid&&c[q+1]+c[mid+1]==c[q+1])++q;
	for(int i=l;i<=q;i++)s2+=c[i].r;
	for(int i=q+1;i<=p;i++)ds2.upd(c[i].u,1),++cnt1,s1+=c[i].r;
	for(int i=mid+1;i<=r;i++)
	{
		while(q>=l&&c[q]+c[i]!=c[q])s2-=c[q].r,++cnt1,s1+=c[q].r,ds2.upd(c[q--].u,1);
		while(p>q&&c[p]+c[i]==c[i])++cnt2,--cnt1,s1-=c[p].r,ds2.upd(c[p--].u,-1);
		ans+=1ll*cnt2*c[i].r+s2+(1ll*cnt1*c[i].r+s1+ds2.query(c[i].u))/2;
	}
	while(p>q)ds2.upd(c[p--].u,-1);
//	cout<<ans-tans<<endl;
}
int main()
{
//	freopen("data.txt","r",stdin);
	scanf("%d",&n);int node_cnt=n;
	for(int i=1,u,v;i<n;i++)
	{
		scanf("%d%d",&u,&v);++node_cnt;
		ade(u,node_cnt),ade(node_cnt,u);
		ade(v,node_cnt),ade(node_cnt,v);
	}
	ds1.build();ds2.build();
//	ds2.print();
	solve(1,n);
	cout<<ans<<endl;
}