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 cs const
#define pb push_back
using namespace std;
typedef long long ll;
cs int N = 2e5 + 50;
int n; vector<int> G[N];
void add(int u, int v){ G[u].pb(v), G[v].pb(u); }

int sz[N], Mx, rt, all; bool ban[N]; 
void gsz(int u, int f){
	sz[u] = 1; for(int v : G[u]) 
	if(!ban[v] && v != f)
	gsz(v, u), sz[u] += sz[v];
} void grt(int u, int f){
	int mx = all - sz[u];
	for(int v : G[u]) if(v != f && !ban[v]) 
	grt(v, u), mx = max(mx, sz[v]); 
	if(mx < Mx) Mx = mx, rt = u; 
} int anc[N], _d[N], d[20][N];
void dfs(int u, int f, int r){
	for(int v : G[u]) 
	if(v != f && !ban[v])
	d[r][v] = d[r][u] + 1, dfs(v, u, r);
} void work(int u, int f){
	gsz(u, 0); Mx = all = sz[u]; grt(u, 0); 
	ban[u = rt] = true;
	_d[u] = _d[anc[u] = f] + 1; 
 	dfs(u, 0, _d[u]);
	for(int v : G[u]) if(!ban[v]) work(v, u);
} 
int c[N]; ll b[N], _b[N];
void ins(int x, int vl){
	for(int u = x, t = _d[x]; u; u = anc[u], --t){
		if(t > 1) _b[u] += vl * d[t - 1][x];
		c[u] += vl, b[u] += vl * d[t][x];
	}
} ll ask(int x){
	ll ans = b[x]; 
	for(int u = x, v = anc[x], t = 
	_d[x] - 1; v; u = v, v = anc[v], --t)
	ans += 1ll * (c[v] - c[u]) * d[t][x] + b[v] - _b[u];
	return ans; 
}

int dep[N], fa[N][20];
void pre_dfs(int u, int f){
	dep[u] = dep[fa[u][0] = f] + 1; 
	for(int i = 1; i <= 17; i++) 
	fa[u][i] = fa[fa[u][i - 1]][i - 1];
	for(int v : G[u]) if(v != f) pre_dfs(v, u);
} int LCA(int x, int y){
	if(dep[x] < dep[y]) swap(x, y);
	for(int i = 17; ~i; i--)
	if(dep[fa[x][i]] >= dep[y]) x = fa[x][i];
	if(x == y) return x;
	for(int i = 17; ~i; i--)
	if(fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
	return fa[x][0];
} int dist(int x, int y){ return dep[x] + dep[y] - 2 * dep[LCA(x, y)]; }
int jmp(int x, int d){ 
	for(int i = 17; ~i; i--)
	if(d >= (1 << i)) d -= 1 << i, x = fa[x][i]; return x; 
} int fnd(int x, int y, int d){
	int l = LCA(x, y);
	if(dep[x] - dep[l] >= d) return jmp(x, d);
	d -= dep[x] - dep[l];
	return jmp(y, dep[y] - dep[l] - d);
}
struct lll{ 
	int u, r;
	lll operator + (cs lll &z) {
		int d = dist(u, z.u);
		if(r + d <= z.r) return z; 
		if(z.r + d <= r) return *this;
		int t = (r + z.r + d) / 2; 
		int p = fnd(u, z.u, t - r);
		return (lll){p, t};
	} bool in(cs lll &z){ return z.r + dist(u, z.u) <= r; }
	bool _in(cs lll &z){ return z.r + dist(u, z.u) < r; }
} p[N]; ll Ans;
void cope(int l, int r){
	if(l == r) return;
	int mid = (l + r) >> 1; 
	p[mid] = (lll){mid, 0};
	p[mid + 1] = (lll){mid + 1, 0};
	for(int i = mid - 1; i >= l; i--)
	p[i] = (lll){i, 0} + p[i + 1];
	for(int i = mid + 2; i <= r; i++)
	p[i] = (lll){i, 0} + p[i - 1];
	int lp = mid, rp = mid + 1; 
	static ll s[N]; s[r + 1] = 0; 
	for(int i = r; i > mid; i--)
	s[i] = s[i + 1] + p[i].r; 
	for(int i = mid; i >= l; i--){
		while(rp <= r && !p[rp].in(p[i])) ins(p[rp].u, 1), ++rp;
		while(lp < r && p[i]._in(p[lp + 1])) ++lp, ins(p[lp].u, -1);
		Ans += s[rp] + 1ll * p[i].r * (lp - mid);
		Ans += (s[lp + 1] - s[rp] + 1ll *
		p[i].r * (rp - lp - 1) + ask(p[i].u)) / 2; 
	} while(lp + 1 < rp) ++lp, ins(p[lp].u, -1);
	cope(l, mid), cope(mid + 1, r);
}
int main(){
	#ifdef FSYo
	freopen("1.in", "r", stdin);
	#endif
	cin >> n;
	for(int i = 1, u, v; i < n; i++)
	scanf("%d%d", &u, &v), 
	add(u, i + n), add(i + n, v);
	pre_dfs(1, 0); work(1, 0);
	cope(1, n);
	cout << Ans << '\n';
}