Problem Statement

You are given a tree with $N$ vertices. The vertices are numbered from $1$ through $N$, and the $i$-th edge connects vertex $A_i$ and vertex $B_i$. Find the number of tuples of integers $(i,j,k)$ such that:

• $1 \leq i < j < k \leq N$; and
• the given tree does not contain a simple path that contains all of vertices $i$, $j$, and $k$.

Constraints

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

Input

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

N
A_1 B_1
\vdots
A_{N-1} B_{N-1}

Output

Print the answer.