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<algorithm>
#include<cstdio>
#include<vector>
#define ll long long
#define pb push_back
#define MaxN 200500
using namespace std;
vector<int> g[MaxN];
struct totode
{int tf,f,son,c;}b[MaxN];
int dep[MaxN];
void pfs1(int u)
{
  b[u].c=1;
  dep[u]=dep[b[u].f]+1;
  for (int i=0,v;i<g[u].size();i++)
    if ((v=g[u][i])!=b[u].f){
   	  b[v].f=u;pfs1(v);
   	  b[u].c+=b[v].c;
   	  if (b[v].c>b[b[u].son].c)
        b[u].son=v;
    }
}
struct Node{
  int f,l,r,tag,c;ll s;
  inline void ladd(int t)
  {tag+=t;s+=1ll*t*c;}
}a[MaxN<<1];int tn;
int st[MaxN],tc[MaxN],tot;
int build(int l,int r)
{
  if (l==r)return st[l];
  int c=0,mid;
  for (int i=l;i<=r;i++)c+=tc[i];
  for (int i=l,c2=0;i<=r;i++){
    c2+=tc[i];
    if (c2+c2>c){mid=i-1;break;}
  }if (mid<l)mid=l;
  a[c=++tn].c=r-l+1;
  return
  a[a[c].l=build(l,mid)].f=
  a[a[c].r=build(mid+1,r)].f=c;
}
int dfn[MaxN],tp[MaxN],tim;
void pfs2(int u,int top)
{
  tp[dfn[u]=++tim]=u;
  b[u].tf=top;
  if (!b[u].son){
    for (tot=0;b[u].tf==top;u=b[u].f)tc[++tot]=u;
    for (int i=1;i<=tot;i++)st[tot-i+1]=tc[i];
    for (int i=1;i<=tot;i++)
      tc[i]=b[st[i]].c-b[b[st[i]].son].c;
    build(1,tot);
    return ;
  }pfs2(b[u].son,top);
  for (int i=0,v;i<g[u].size();i++)
    if ((v=g[u][i])!=b[u].f&&v!=b[u].son)
   	  pfs2(v,v);
}
inline void up(int u)
{a[u].s=a[a[u].l].s+a[a[u].r].s;}
inline void ladd(int u){
  if (a[u].tag){
    a[a[u].l].ladd(a[u].tag);
    a[a[u].r].ladd(a[u].tag);
    a[u].tag=0;
  }
}
void grt(int u){
  for (tot=0;u;u=a[u].f)st[++tot]=u;
  for (int i=tot;i>1;i--)ladd(st[i]);
}
void add(int u,int w){
  grt(u);
  a[st[1]].ladd(w);
  for (int i=2,v;i<=tot;i++){
    if ((v=a[st[i]].l)!=st[i-1])
      a[v].ladd(w);
    up(st[i]);
  }
}
ll sum;
void qry(int u){
  grt(u);ll las=sum;
  sum+=a[st[1]].s;
  for (int i=2,v;i<=tot;i++)
    if ((v=a[st[i]].l)!=st[i-1])
      sum+=a[v].s;
}
void padd(int x,int w)
{while(x){add(x,w);x=b[b[x].tf].f;}}
ll pqry(int x){
  sum=0;
  while(x){qry(x);x=b[b[x].tf].f;}
  return sum;
}
int lca(int u,int v)
{
  while(b[u].tf!=b[v].tf){
    if (dep[b[v].tf]>dep[b[u].tf])swap(u,v);
    u=b[b[u].tf].f;
  }return dep[u]<dep[v] ? u:v;
}
int dis(int u,int v)
{return dep[u]+dep[v]-2*dep[lca(u,v)];}
int up(int u,int d){
  while(dep[b[u].tf]>d)u=b[b[u].tf].f;
  return tp[dfn[b[u].tf]+d-dep[b[u].tf]];
}
int lin(int u,int v,int l)
{
  int t=lca(u,v);
  if (dep[u]-dep[t]>=l)return up(u,dep[u]-l);
  return up(v,l-dep[u]+2*dep[t]);
}
struct Data{int u,r;}s[MaxN];
Data merge(const Data &A,int u)
{
  int d=dis(A.u,u);
  if (d<=A.r)return A;
  return (Data){lin(A.u,u,(d-A.r)/2),(d+A.r)/2};
}
bool in(const Data &A,const Data &B)
{return A.r+dis(A.u,B.u)<=B.r;}
ll ans,o[MaxN],o2[MaxN];
Data q[MaxN];int tq;
bool cmpQ(const Data &A,const Data &B)
{return A.r<B.r;}
void solve(int L,int R)
{
  if (L==R)return ;
  int mid=(L+R)>>1;
  solve(L,mid);solve(mid+1,R);
  s[mid]=(Data){mid,0};
  s[mid+1]=(Data){mid+1,0};
  for (int l=mid-1;l>=L;l--)
    s[l]=merge(s[l+1],l);
  for (int r=mid+2;r<=R;r++)
    s[r]=merge(s[r-1],r);
  o[mid]=0;
  for (int r=mid+1;r<=R;r++){
    o[r]=o[r-1]+s[r].r;
    o2[r]=o2[r-1]+dep[s[r].u];
  }
  int p1=mid,p2=mid;
  tq=0;
  for (int l=mid;l>=L;l--){
    while(p1<R&&in(s[p1+1],s[l]))p1++;
    while(p2<R&&!in(s[l],s[p2+1]))p2++;
    p2=max(p2,p1);
    ans+=2ll*(p1-mid)*s[l].r+2*(o[R]-o[p2])
        +1ll*(p2-p1)*s[l].r+(o[p2]-o[p1])
        +1ll*(p2-p1)*dep[s[l].u]+(o2[p2]-o2[p1]);
    if (p1<p2){
      if (p1>mid)q[++tq]=(Data){-s[l].u,p1};
      q[++tq]=(Data){s[l].u,p2};
    }
  }sort(q+1,q+tq+1,cmpQ);
  for (int i=mid+1,p=1;i<=R;i++){
    padd(s[i].u,1);
    while(p<=tq&&q[p].r==i){
      if (q[p].u<0)ans+=2*pqry(-q[p].u);
      else ans-=2*pqry(q[p].u);
      p++;
    }
  }for (int i=mid+1;i<=R;i++)padd(s[i].u,-1);
}
int n;
int main()
{
  scanf("%d",&n);tn=n*2-1;
  for (int i=1;i<=tn;i++)a[i].c=1;
  for (int i=1,u,v;i<n;i++){
    scanf("%d%d",&u,&v);
    g[u].pb(n+i);g[n+i].pb(u);
    g[v].pb(n+i);g[n+i].pb(v);
  }pfs1(1);pfs2(1,1);
  solve(1,n);
  printf("%lld\n",ans>>1);
  return 0;
}