Problem Statement

We have a tree with $N$ vertices and $N-1$ edges, respectively numbered $1, 2,\cdots, N$ and $1, 2, \cdots, N-1$. Edge $i$ connects Vertex $u_i$ and $v_i$.

For integers $L, R$ ($1 \leq L \leq R \leq N$), let us define a function $f(L, R)$ as follows:

• Let $S$ be the set of the vertices numbered $L$ through $R$. $f(L, R)$ represents the number of connected components in the subgraph formed only from the vertex set $S$ and the edges whose endpoints both belong to $S$.

Compute $\sum_{L=1}^{N} \sum_{R=L}^{N} f(L, R)$.

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq u_i, v_i \leq N$
• The given graph is a tree.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
u_1 v_1
u_2 v_2
:
u_{N-1} v_{N-1}

Output

Print $\sum_{L=1}^{N} \sum_{R=L}^{N} f(L, R)$.