Ana and Bob are playing a game on a tree with $n$ vertices.

First, two distinct vertices $p$ and $q$ are chosen, and the game starts with the simple path between them. The vertex $p$ is Ana's endpoint and $q$ is Bob's endpoint. The players then take turns, starting with Ana:

• On her turn, Ana must choose a neighbor $p'$ of $p$ that does not lie on the current path. The path is extended to $p'$, and $p'$ becomes Ana's new endpoint.
• On his turn, Bob must choose a neighbor $q'$ of $q$ that does not lie on the current path. The path is extended to $q'$, and $q'$ becomes Bob's new endpoint.

The player who cannot make a move loses.

Count the ordered pairs $(p, q)$ with $p \ne q$ for which Ana wins, assuming both players play optimally.

Input

The first line contains a single integer $n$ ($2 \le n \le 10^6$), the number of vertices in the tree.

Each of the next $n - 1$ lines contains two integers $u$ and $v$ ($1 \le u, v \le n$, $u \ne v$), meaning there is an edge between vertices $u$ and $v$. It is guaranteed that the given edges form a tree.

Date de ieșire

Print a single integer: the number of ordered pairs $(p, q)$ for which Ana wins.

Example

stdin

5
1 3
2 3
4 3
5 1

stdout

6

Note

Ana wins for the following $6$ pairs:

• $(1, 2)$: the path is $1 - 3 - 2$. Ana extends it to vertex $5$. The only neighbor of $2$ is $3$, which is already on the path, so Bob cannot move.
• $(1, 4)$: symmetric to the previous case.
• $(1, 5)$: the path is $1 - 5$. Ana extends it to vertex $3$. The only neighbor of $5$ is $1$, which is already on the path, so Bob cannot move.
• $(3, 2)$: the path is $3 - 2$. Ana extends it to vertex $1$ or $4$, and Bob has no move from vertex $2$.
• $(3, 4)$: symmetric to the previous case.
• $(3, 5)$: the path is $3 - 1 - 5$. Ana extends it to vertex $2$ or $4$, and Bob has no move from vertex $5$.

For example, Ana loses for $(1, 3)$. The path is $1 - 3$, and Ana's only move is to vertex $5$. Bob then extends the path to vertex $2$. Ana's endpoint $5$ has no neighbor outside the path, so she cannot move and loses.