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>
using namespace std;
#define ll long long
const int maxn = 200005;
int n, m;
int last[maxn], Next[maxn << 1], to[maxn << 1], cnt;
inline void addedge(int x, int y) {
	Next[++cnt] = last[x];
	last[x] = cnt, to[cnt] = y;
}
int dep[maxn], fa[maxn][18], Log[maxn];
void dfs(int x) {
	dep[x] = dep[fa[x][0]] + 1;
	for(int i = 1; i <= Log[dep[x]]; i++) fa[x][i] = fa[fa[x][i - 1]][i - 1];
	for(int i = last[x]; i; i = Next[i]) {
		int v = to[i];
		if(v != fa[x][0]) {
			fa[v][0] = x;
			dfs(v);
		}
	} 
}
int getlca(int x, int y) {
	if(dep[x] < dep[y]) swap(x, y);
	int l = dep[x] - dep[y];
	for(int i = Log[l]; i >= 0; i--)
		if((l >> i) & 1) x = fa[x][i];
	if(x == y) return x;
	for(int i = Log[dep[x]]; i >= 0; 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] - dep[getlca(x, y)] * 2; }
int jump(int x, int d) {
	for(int i = Log[d]; i >= 0; i--)
		if((d >> i) & 1) x = fa[x][i];
	return x;
}
struct circle {
	int v, r;
	circle(int _v = 0, int _r = 0) { v = _v, r = _r; }
};
bool contain(circle a, circle b) {
	if(b.r < a.r) return 0;
	return dist(a.v, b.v) <= b.r - a.r;
}
circle merge(circle a, circle b) {
	if(a.r > b.r) swap(a, b);
	int x = a.v, y = b.v, lca = getlca(x, y);
	int dis = dep[x] + dep[y] - dep[lca] * 2;
	if(dis <= b.r - a.r) return b;
	int r = (a.r + b.r + dis) / 2;
	int d1 = r - a.r, d2 = r - b.r;
	assert(d1 <= dep[x] - dep[lca] || d2 <= dep[y] - dep[lca]);
	int v = (d1 <= dep[x] - dep[lca]) ? jump(x, d1) : jump(y, d2);
	return circle(v, r);
}

namespace divtree {
	int vis[maxn];
	int size[maxn], minp[maxn], totsz, rt;
	void getrt(int x, int fa) {
		size[x] = 1;
		minp[x] = 0;
		for(int i = last[x]; i; i = Next[i]) {
			int v = to[i];
			if(v != fa && !vis[v]) {
				getrt(v, x);
				size[x] += size[v];
				minp[x] = max(minp[x], size[v]);
			}
		}
		minp[x] = max(minp[x], totsz - size[x]);
		if(minp[x] < minp[rt]) rt = x;
	}
	int fa[maxn], dis[maxn][20];
	void solve(int x) {
		vis[x] = 1;
		for(int i = last[x]; i; i = Next[i]) {
			int v = to[i];
			if(!vis[v]) {
				getrt(v, x);
				rt = 0, totsz = size[v];
				getrt(v, x);
				fa[rt] = x;
				solve(rt);
			}
		}
	}
	void build() {
		totsz = minp[0] = n;
		getrt(1, 0);
		solve(rt);
		for(int i = 1; i <= n; i++)
			for(int j = 0, x = i; x; j++, x = fa[x]) dis[i][j] = dist(i, x);
	}
	int cnt[maxn][2];
	ll sum[maxn][2];
	void change(int x, int v) {
		for(int i = 0, y = x; y; i++, y = fa[y]) {
			int d = dis[x][i];
			sum[y][0] += d * v, cnt[y][0] += v;
			if(fa[y]) {
				d = dis[x][i + 1];
				sum[y][1] += d * v, cnt[y][1] += v;
			}
		}
	}
	ll query(int x) {
		ll res = 0;
		for(int i = 0, y = x; y; i++, y = fa[y]) {
			res += sum[y][0] + 1ll * cnt[y][0] * dis[x][i];
			if(fa[y]) res -= sum[y][1] + 1ll * cnt[y][1] * dis[x][i + 1];
		}
		return res;
	}
}
using divtree :: change;

circle A[maxn];
ll sum[maxn];
ll solve(int l, int r) {
	if(l == r) return 0;
	int mid = (l + r) >> 1;
	ll res = solve(l, mid) + solve(mid + 1, r);
	
	A[mid + 1] = circle(mid + 1, 0);
	sum[mid] = sum[mid + 1] = 0;
	for(int i = mid + 2; i <= r; i++) {
		A[i] = merge(A[i - 1], circle(i, 0));
		sum[i] = sum[i - 1] + A[i].r;
	}
	
	int L = mid + 1, R = mid;
	circle now = circle(mid, 0);
	for(int i = mid; i >= l; i--) {
		now = merge(now, circle(i, 0));
		while(R < r && !contain(now, A[R + 1])) R++, change(A[R].v, 1);
		while(L <= R && contain(A[L], now)) change(A[L].v, -1), L++;
		assert(R - L + 1 >= 0);
		res += 1ll * (L - mid - 1) * now.r;
		res += (sum[R] - sum[L - 1] + 1ll * (R - L + 1) * now.r + divtree :: query(now.v)) / 2;
		res += sum[r] - sum[R]; 
	}
	
	for(int i = L; i <= R; i++) change(A[i].v, -1);
	return res;
}

int main() {
	scanf("%d", &n);
	for(int i = 1, x, y, z; i < n; i++) {
		scanf("%d%d", &x, &y);
		z = n + i;
		addedge(x, z), addedge(z, x);
		addedge(z, y), addedge(y, z);
	}
	m = n;
	n += n - 1;
	for(int i = 2; i <= n; i++) Log[i] = Log[i >> 1] + 1;
	dfs(1);
	divtree :: build();
	cout << solve(1, m) << endl;
	return 0;
}