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;
int gi() {
	int res = 0, w = 1;
	char ch = getchar();
	while (ch != '-' && !isdigit(ch)) ch = getchar();
	if (ch == '-') w = -1, ch = getchar();
	while (isdigit(ch)) res = res * 10 + ch - '0', ch = getchar();
	return res * w;
}
typedef long long LL;
const int MAX_N = 2e5 + 5;
vector<int> G[MAX_N];
int N, top[MAX_N], siz[MAX_N], dep[MAX_N], fa[MAX_N], son[MAX_N];
int L[MAX_N], R[MAX_N], dfn[MAX_N], tim;
void dfs1(int x) {
	siz[x] = 1, dep[x] = dep[fa[x]] + 1;
	for (int v : G[x]) {
		if (v == fa[x]) continue;
		fa[v] = x, dfs1(v), siz[x] += siz[v];
		if (siz[son[x]] < siz[v]) son[x] = v;
	}
}
void dfs2(int x, int tp) {
	top[x] = tp, dfn[L[x] = ++tim] = x;
	if (son[x]) dfs2(son[x], tp);
	for (int v : G[x]) {
		if (v == son[x] || v == fa[x]) continue;
		dfs2(v, v);
	}
	R[x] = tim;
}
int LCA(int x, int y) {
	while (top[x] != top[y]) {
		if (dep[top[x]] < dep[top[y]]) swap(x, y);
		x = fa[top[x]];
	}
	return dep[x] < dep[y] ? x : y;
}
int Jump(int x, int k) {
	while (k) {
		if (dep[x] - dep[fa[top[x]]] <= k) k -= (dep[x] - dep[fa[top[x]]]), x = fa[top[x]];
		else x = dfn[L[x] - k], k = 0;
	}
	return x;
}
struct node { int x, r; } pre[MAX_N];
bool operator == (const node &a, const node &b) { return a.x == b.x && a.r == b.r; }
bool operator != (const node &a, const node &b) { return a.x != b.x || a.r != b.r; }
bool in(const node &a, const node &b) {
	int d = dep[a.x] + dep[b.x] - 2 * dep[LCA(a.x, b.x)];
	if (b.r + d <= a.r) return 1;
	else return 0;
}
int calc_point(int u, int v, int d) {
	int w = LCA(u, v);
	if (dep[u] - dep[w] >= d) return Jump(u, d);
	else return Jump(v, dep[u] + dep[v] - 2 * dep[w] - d);
}
node operator + (const node &a, const node &b) {
	int d = dep[a.x] + dep[b.x] - 2 * dep[LCA(a.x, b.x)];
	if (d + a.r <= b.r) return b;
	if (d + b.r <= a.r) return a;
	return (node){calc_point(a.x, b.x, (d + b.r - a.r) / 2), (d + b.r + a.r) / 2};
}
namespace Bit {
	LL c1[MAX_N], c2[MAX_N];
	int lb(int x) { return x & -x; }
	void add(LL c[], int x, LL v) { for (; x <= tim; x += lb(x)) c[x] += v; }
	LL sum(LL c[], int x) { LL res = 0; for (; x; x -= lb(x)) res += c[x]; return res; }
	void Add(int x, int v) { add(c1, x, v), add(c2, x, 1ll * v * x); }
	LL Sum(int x) { return sum(c1, x) * (x + 1) - sum(c2, x); }
}
void mdf(int x, int v) {
	while (x) {
		int l = L[top[x]], r = L[x];
		Bit::Add(l, v), Bit::Add(r + 1, -v);
		x = fa[top[x]];
	}
}
LL qry(int x) {
	LL res = 0;
	while (x) {
		int l = L[top[x]], r = L[x];
		res += Bit::Sum(r) - Bit::Sum(l - 1);
		x = fa[top[x]];
	}
	return res;
}
LL sr[MAX_N], sd[MAX_N], ans;
void Div(int l, int r) {
	if (l == r) return ;
	int mid = (l + r) >> 1;
	sr[mid] = sd[mid] = 0, pre[mid + 1] = (node){mid + 1, 0};
	for (int i = mid + 2; i <= r; i++) pre[i] = pre[i - 1] + (node){i, 0};
	for (int i = mid + 1; i <= r; i++) sr[i] = sr[i - 1] + pre[i].r;
	for (int i = mid + 1; i <= r; i++) sd[i] = sd[i - 1] + dep[pre[i].x];
	node now = (node){mid, 0};
	int p = mid + 1, q = mid + 1;
	for (int i = mid; i >= l; i--) {
		now = now + (node){i, 0};
		while (p <= r && in(now, pre[p])) mdf(pre[p].x, -1), ++p;
		while (q <= r) {
			if (now == pre[q] || !in(pre[q], now)) mdf(pre[q].x, 1), ++q;
			else break;
		}
		ans += 2ll * (p - mid - 1) * now.r;
		ans += 2 * (sr[r] - sr[q - 1]);
		ans += sr[q - 1] - sr[p - 1] + sd[q - 1] - sd[p - 1] + 1ll * (q - p) * (now.r + dep[now.x]) - 2 * qry(now.x);;
	}
	for (int i = p; i < q; i++) mdf(pre[i].x, -1);
	Div(l, mid), Div(mid + 1, r);
}
int main () {
#ifndef ONLINE_JUDGE
    freopen("cpp.in", "r", stdin);
#endif
	N = gi();
	for (int i = 1; i < N; i++) {
		int u = gi(), v = gi();
		G[u].push_back(i + N), G[i + N].push_back(u);
		G[v].push_back(i + N), G[i + N].push_back(v);
	}
	dfs1(1), dfs2(1, 1);
	Div(1, N);
	printf("%lld\n", ans / 2);
    return 0;
}