Problem Statement

You are given a tree $T$ with $N$ vertices. The vertices are numbered from $0$ to $N-1$, and the $i$-th edge $(1\le i\le N-1)$ bidirectionally connects vertices $u_i$ and $v_i$. (Note that vertex numbers are 0-indexed and edge numbers are 1-indexed.)

For a pair of integers $(i,j)$ where $0 \leq i,j < N$, define $f(i,j)$ as follows:

• The vertex number of the vertex with the smallest number among the vertices not included in the path from vertex $i$ to vertex $j$ in tree $T$.
• Here, if the path from vertex $i$ to vertex $j$ includes all vertices from vertex $0$ to vertex $N-1$, let $f(i,j)=N$.

Note that the path from vertex $i$ to vertex $j$ in tree $T$ includes vertices $i$ and $j$.

Find the value of $\displaystyle \sum_{0\le i \le j < N} f(i,j)$.

Constraints

• $2\le N\le 2\times 10^5$
• $0\le u_i < v_i < N$
• The graph given in the input is a tree.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}

Output

Output the value of $\displaystyle \sum_{0\le i \le j < N} f(i,j)$.