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<cstdio>
#include<vector>

using namespace std;

int n;vector<int> ed[800000];

namespace DT // decomposition tree
{
	int level,rt[20][800000],fa_pnt[800000],dep[20][800000],lv[800000];
	bool is_ctr[800000];
	vector<int> pnt;
	int sz[800000],maxsz[800000];
	void dfs(int u,int f,int r,int level)
	{
		rt[level][u]=r,dep[level][u]=f?dep[level][f]+1:0;pnt.push_back(u);
		sz[u]=1,maxsz[u]=0;
		for(int i=0;i<ed[u].size();i++)
		{
			int v=ed[u][i];if(is_ctr[v]||v==f)continue;
			dfs(v,u,r,level);sz[u]+=sz[v],maxsz[u]=max(maxsz[u],sz[v]);
		}
	}
	void pre_compute()
	{
		level=0;
		while(1)
		{
			bool fl=1;for(int i=1;i<=2*n;i++)if(!is_ctr[i]){fl=0;break;}if(fl)break;
			level++;
			for(int i=1;i<=2*n;i++)
			{
				if(!is_ctr[i]&&!rt[level][i])
				{
					pnt.clear();
					dfs(i,0,i,level);
					int r=i;
					for(int i=0;i<pnt.size();i++)
					{
						int u=pnt[i];
						if(max(maxsz[r],(int)pnt.size()-sz[r])>max(maxsz[u],(int)pnt.size()-sz[u]))r=u;
					}
					is_ctr[r]=1;lv[r]=level;fa_pnt[r]=rt[level-1][r];
					dfs(r,0,r,level);
				}
			}
		}
	}
	long long cnt[800000],sumdep[800000][2];
	void add(int u,long long val)
	{
		int x=u,l=lv[u];
		while(u)
		{
			cnt[u]+=val;sumdep[u][0]+=dep[l][x]*val;if(l>1)sumdep[u][1]+=dep[l-1][x]*val;
			u=fa_pnt[u],l--;
		}
	}
	long long query(int u)
	{
		//printf("QUERY: %d\n",u);
		int x=u,l=lv[u];long long ans=0;
		while(u!=0)
		{
			//printf("%d\n",u);
			ans+=cnt[u]*dep[l][x]+sumdep[u][0];if(l>1)ans-=cnt[u]*dep[l-1][x]+sumdep[u][1];
			u=fa_pnt[u],l--;
		}
		return ans;
	}
}

int fa[800000][20],dep[800000];
void dfs_bas(int u,int f)
{
	fa[u][0]=f,dep[u]=f?dep[f]+1:0;for(int i=1;i<20;i++)fa[u][i]=fa[fa[u][i-1]][i-1];
	for(int i=0;i<ed[u].size();i++){if(ed[u][i]!=f)dfs_bas(ed[u][i],u);}
}
int LCA(int x,int y)
{
	if(dep[x]<dep[y])swap(x,y);for(int i=19;i>=0;i--)if(dep[fa[x][i]]>=dep[y])x=fa[x][i];if(x==y)return x;
	for(int i=19;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];return fa[x][0];
}
int dis(int x,int y){return dep[x]+dep[y]-2*dep[LCA(x,y)];}
int anc(int x,int d)
{
	for(int i=19;i>=0;i--)if(d&(1<<i))x=fa[x][i];return x;
}
int walk_dis(int x,int y,int d) // returns the d-th node on the path from x to y
{
	int l=LCA(x,y),D=dep[x]+dep[y]-2*dep[l];
	if(d<=dep[x]-dep[l])return anc(x,d);return anc(y,D-d);
}

struct cir
{
	int v,r;cir(int vv=0,int rr=0):v(vv),r(rr){}
};
cir merge(cir A,cir B)
{
	int d=dis(A.v,B.v);if(d+A.r<=B.r)return B;if(d+B.r<=A.r)return A;
	return cir(walk_dis(A.v,B.v,(d-A.r+B.r)>>1),(d+A.r+B.r)>>1);
}
int status_cir(cir A,cir B)
{
	int d=dis(A.v,B.v);if(d+A.r<=B.r)return 2;if(d+B.r<=A.r)return 0;return 1;
}

cir C[800000];long long s[800000];

long long solve(int l,int r)
{
	//printf("SOLVE: %d %d\n",l,r);
	if(l>=r)return 0;
	int mid=(l+r)>>1;long long ans=0;
	for(int i=l;i<=r;i++)C[i]=cir(i,0);
	for(int i=mid-1;i>=l;i--)C[i]=merge(C[i],C[i+1]);
	for(int i=mid+2;i<=r;i++)C[i]=merge(C[i],C[i-1]);
	//for(int i=l;i<=r;i++)printf("%d %d\n",C[i].v,C[i].r);
	//return 0;
	s[mid]=0;for(int i=mid+1;i<=r;i++)s[i]=s[i-1]+C[i].r;
	int r1=mid+1,r2=mid+1;
	for(int i=mid;i>=l;i--)
	{
		while(r2<=r&&status_cir(C[i],C[r2])<2){DT::add(C[r2].v,+1);r2++;}
		while(r1<=r&&status_cir(C[i],C[r1])<1){DT::add(C[r1].v,-1);r1++;}
		ans+=s[r]-s[r2-1];
		ans+=(long long)C[i].r*(r1-mid-1);
		long long tmp=(long long)C[i].r*(r2-r1);tmp+=s[r2-1]-s[r1-1];
		//printf("QUERY %d\n",C[i].v);
		tmp+=DT::query(C[i].v);ans+=tmp/2;
	}
	for(int i=r1;i<r2;i++)DT::add(C[i].v,-1);
	//puts("OK");return 0;
	ans+=solve(l,mid),ans+=solve(mid+1,r);
	return ans;
}

int main()
{
	scanf("%d",&n);
	for(int i=1,u=0,v=0;i<n;i++)
	{
		scanf("%d%d",&u,&v);ed[u].push_back(i+n),ed[v].push_back(i+n);ed[i+n].push_back(u),ed[i+n].push_back(v);
	}
	dfs_bas(1,0);DT::pre_compute();//puts("OK");return 0;
	printf("%lld",solve(1,n));
}