13:I[87,["736","static/chunks/89fc4f0e-9e200ae6a0166583.js","401","static/chunks/363642f4-32903b9154b7835a.js","153","static/chunks/153-58eddeb032cc4608.js","131","static/chunks/131-05ce00cfd760e12b.js","87","static/chunks/87-b76b60eef573119a.js","286","static/chunks/app/problem/%5Bid%5D/page-45cf3875257fc32e.js"],"Header"] 14:I[1742,["736","static/chunks/89fc4f0e-9e200ae6a0166583.js","401","static/chunks/363642f4-32903b9154b7835a.js","153","static/chunks/153-58eddeb032cc4608.js","131","static/chunks/131-05ce00cfd760e12b.js","87","static/chunks/87-b76b60eef573119a.js","286","static/chunks/app/problem/%5Bid%5D/page-45cf3875257fc32e.js"],"ProblemView"] 15:T573,

You are given a tree with $$$n$$$ vertices numbered $$$1, \ldots, n$$$. A tree is a connected simple graph without cycles.

Let $$$\mathrm{dist}(u, v)$$$ be the number of edges in the unique simple path connecting vertices $$$u$$$ and $$$v$$$.

Let $$$\mathrm{diam}(l, r) = \max \mathrm{dist}(u, v)$$$ over all pairs $$$u, v$$$ such that $$$l \leq u, v \leq r$$$.

Compute $$$\sum_{1 \leq l \leq r \leq n} \mathrm{diam}(l, r)$$$.

Input

The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 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 \leq u, v \leq n$$$) — endpoint indices of the respective tree edge. It is guaranteed that the edge list indeed describes a tree.

Output

Print a single integer — $$$\sum_{1 \leq l \leq r \leq n} \mathrm{diam}(l, r)$$$.

Range Diameter Sum

Examples