H. Heritage Hunt
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The Maratona Mineira team is organizing a treasure hunt. The treasure will be two chests of the most delicious doce de leite in the world, a cultural heritage of Minas Gerais, which will be hidden on the game map.

The map consists of $$$N$$$ vertices, numbered from $$$1$$$ to $$$N$$$, and $$$N - 1$$$ edges, in such a way that it is possible to go from any vertex to any other. In other words, the map forms a tree. The distance between two vertices is defined as the number of edges in the unique simple path between them.

The team already has the map, but still needs to choose in which vertices to hide the two chests. A choice is considered valid if the chests are placed on distinct vertices and the number of vertices closer to the first chest is equal to the number of vertices closer to the second chest. Vertices at the same distance from both chests do not count towards either one.

The figure above shows a valid choice for Example 1. The chests were placed at vertices $$$1$$$ and $$$7$$$. Thus, vertices $$$1$$$, $$$2$$$, and $$$3$$$ (red circles) are closer to the chest at vertex $$$1$$$, while vertices $$$5$$$, $$$6$$$, and $$$7$$$ (blue diamonds) are closer to the chest at vertex $$$7$$$. Vertex $$$4$$$ (yellow star) is at the same distance from both chests.

Determine the number of valid ways to choose the positions of the chests. Two ways are considered distinct if the set of vertices where a chest was placed is different.

Input

The first line of the input contains an integer $$$N$$$ ($$$2 \leq N \leq 2 \times 10^{5}$$$), the number of vertices in the map.

Each of the next $$$N - 1$$$ lines contains two integers $$$u_{i}$$$ and $$$v_{i}$$$ ($$$1 \leq u_{i}, v_{i} \leq N$$$, $$$u_{i} \neq v_{i}$$$), indicating that there is an edge between vertices $$$u_{i}$$$ and $$$v_{i}$$$. It is guaranteed that the edges form a tree.

Output

Print a single integer: the number of distinct valid ways to choose the positions of the two chests.

Examples
Input
7
1 2
1 3
3 4
4 5
5 6
5 7
Output
4
Input
7
1 2
1 3
3 4
1 5
5 6
6 7
Output
0
Note

Explanation for example 1

The $$$4$$$ valid choices, represented by the positions of the chests, are: $$$\{1, 7\}$$$, $$$\{1, 6\}$$$, $$$\{3, 5\}$$$, and $$$\{6, 7\}$$$.

Explanation for example 2

In this example, there are no valid choices for the positions of the chests.