A matching in a graph $G = (V, E)$ is a subset $M$ of its edges such that no two edges in $M$ share a common endpoint.

An unordered pair $(u, v)$ of vertices of graph $G$ ($u \neq v, (u, v) \notin E$) is called promising if adding the edge $(u, v)$ to $G$ increases the size of the maximum matching in $G$.

Given a connected* graph $G$ with $n$ vertices and $n - 1$ edges, find the number of promising pairs of vertices in $G$.

Input

The first line of input contains a single integer $n$ ($1 \leq n \leq 200\,000$), representing the number of vertices in graph $G$. The next $n - 1$ lines contain descriptions of the edges of $G$. The $i$-th of these lines contains two integers $a_i, b_i$ ($1 \leq a_i, b_i \leq n$), indicating that the $i$-th edge connects vertices $a_i$ and $b_i$. We assume that the vertices of graph $G$ are numbered with integers from $1$ to $n$.

Output

Output a single integer – the number of promising pairs of vertices in $G$.

Examples

Input 1

6
1 2
1 3
1 4
1 5
2 6

Output 1

3

Note

The only promising pairs of vertices are $(3, 4)$, $(3, 5)$, and $(4, 5)$.

*A graph $G$ is connected if every two vertices of $G$ are connected by a path consisting of edges of $G$.