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 <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
const int L = 19;

int n, ts;
vector<int> g[N];
int sz[N], cdFa[N], occur[N];
ll val[N], upval[N];
bool del[N];
int first[N], st[N << 1][L + 1];
int h[N], fa[N][L];

void dfs1(int u, int p)
{
    h[u] = h[p] + 1;
    fa[u][0] = p;
    first[u] = ++ts;
    st[ts][0] = h[u];
    for (int v : g[u])
        if (v != p)
        {
            dfs1(v, u);
            st[++ts][0] = h[u];
        }
}

void prepareLCA(int n)
{
    dfs1(1, 0);
    for (int i = 1; i < L; ++i)
        for (int u = 1; u <= n; ++u)
            fa[u][i] = fa[fa[u][i-1]][i-1];
}

void prepareST()
{
    for (int i = 1; i <= L; ++i)
        for (int j = 1, k = 1 + (1 << (i - 1)); k <= ts; ++j, ++k)
            st[j][i] = min(st[j][i-1], st[k][i-1]);
}

int lcaHeight(int u, int v)
{
    if (u == v) return h[u];
    u = first[u];
    v = first[v];
    if (u > v) swap(u, v);
    int level = 31 - __builtin_clz(v - u);
    return min(st[u][level], st[v - (1 << level) + 1][level]);
}

inline int up(int u, int d)
{
    for (int i = 0; i < L; ++i)
        if (d >> i & 1) u = fa[u][i];
    return u;
}

inline int dist(int u, int v)
{
    return h[u] + h[v] - (lcaHeight(u, v) << 1);
}

inline int go(int u, int v, int d)
{
    int hLCA = lcaHeight(u, v);
    if (h[u] - hLCA >= d) return up(u, d);
    return up(v, h[u] + h[v] - (hLCA << 1) - d);
}

inline bool contain(const pair<int, int> &c1, const pair<int, int> &c2)
{
    return dist(c1.first, c2.first) <= c1.second - c2.second;
}

pair<int, int> Merge(const pair<int, int> &c1, const pair<int, int> &c2)
{
    int d = dist(c1.first, c2.first);
    if (d <= c1.second - c2.second) return c1;
    return {go(c1.first, c2.first, (d - c1.second + c2.second) >> 1), (d + c1.second + c2.second) >> 1};
}

int dfs(int u, int p)
{
    sz[u] = 1;
    for (int v : g[u])
        if (v != p && !del[v])
            sz[u] += dfs(v, u);
    return sz[u];
}

int getCentroid(int u, int p, int lim)
{
    for (int v : g[u])
        if (v != p && !del[v] && sz[v] > lim)
            return getCentroid(v, u, lim);
    return u;
}

void centroidDecomposition(int u, int p)
{
    int n = dfs(u, p);
    int centroid = getCentroid(u, p, n >> 1);
    cdFa[centroid] = p;
    del[centroid] = true;
    for (int v : g[centroid])
        if (v != p && !del[v])
            centroidDecomposition(v, centroid);
}

void add(int u, int coef)
{
    occur[u] += coef;
    for (int p, v = u; (p = cdFa[v]); v = p)
    {
        occur[p] += coef;
        ll delta = dist(p, u) * coef;
        val[p] += delta;
        upval[v] += delta;
    }
}

ll query(int u)
{
    ll res = val[u];
    for (int p, v = u; (p = cdFa[v]); v = p)
        res += (val[p] - upval[v]) + dist(p, u) * ll(occur[p] - occur[v]);
    return res;
}

pair<int, int> prefixCover[N], suffixCover[N];
ll prefixSum[N];

ll solve(int l, int r)
{
    if (l == r) return 0;
    int mid = (l + r) >> 1;
    suffixCover[mid] = {mid, 0};
    for (int i = mid - 1; i >= l; --i)
        suffixCover[i] = Merge(suffixCover[i + 1], {i, 0});
    prefixCover[mid + 1] = {mid + 1, 0};
    prefixSum[mid + 1] = 0;
    for (int i = mid + 2; i <= r; ++i)
    {
        prefixCover[i] = Merge(prefixCover[i - 1], {i, 0});
        prefixSum[i] = prefixSum[i - 1] + prefixCover[i].second;
    }
    ll ans = 0;
    int t1 = mid + 1, t2 = mid + 1;
    for (int i = mid; i >= l; --i)
    {
        while (t2 <= r && !contain(prefixCover[t2], suffixCover[i])) add(prefixCover[t2++].first, 1);
        while (t1 <= r && contain(suffixCover[i], prefixCover[t1])) add(prefixCover[t1++].first, -1);
        while (t1 > t2) add(prefixCover[t2++].first, 1);
        ans += 2ll * (t1 - (mid + 1)) * suffixCover[i].second;
        ans += 2ll * (prefixSum[r] - (t2 > mid + 1 ? prefixSum[t2-1] : 0));
        ans += ll(t2 - t1) * suffixCover[i].second + ((t2 > mid + 1 ? prefixSum[t2-1] : 0) - (t1 > mid + 1 ? prefixSum[t1-1] : 0));
        ans += query(suffixCover[i].first);
    }
    while (t1 < t2) add(prefixCover[t1++].first, -1);
    return ans + solve(l, mid) + solve(mid + 1, r);
}

int main()
{
    scanf("%d", &n);
    for (int x, y, m = n, i = 1; i < n; ++i)
    {
        scanf("%d%d", &x, &y);
        ++m;
        g[x].push_back(m);
        g[y].push_back(m);
        g[m].push_back(x);
        g[m].push_back(y);
    }
    prepareLCA((n << 1) - 1);
    prepareST();
    centroidDecomposition(1, 0);
    printf("%lld\n", solve(1, n) >> 1);
    return 0;
}