Problem Description

In a secure network, there are $n$ communication base stations. They are connected by $n-1$ bidirectional optical fibers and form a tree.

In this problem, base station $1$ is used as the root of the whole tree. For any base station $x$, if the total number of base stations in the subtree rooted at $x$ is even, then base station $x$ is called a stable base station. The subtree here includes base station $x$ itself.

For two different base stations $x$ and $y$, if all base stations on the simple path from $x$ to $y$ are stable base stations, then the ordered path $x \to y$ is called a safe path.

Please compute the total number of safe paths in the whole tree.

Note that $x \to y$ and $y \to x$ are considered two different safe paths.

Input Format

The first line contains a positive integer $n$, representing the number of base stations.

The next $n-1$ lines each contain two positive integers $u, v$, indicating that there is a bidirectional optical fiber between base station $u$ and base station $v$.

The input guarantees that the given $n$ base stations and $n-1$ optical fibers form a tree.

Output Format

Output one line containing an integer, representing the total number of safe paths.

6
1 2
1 3
1 6
2 4
3 5

6

Hint

Sample Explanation

When taking base station $1$ as the root:

• The subtree of base station $2$ contains base stations $2,4$, with size $2$;
• The subtree of base station $3$ contains base stations $3,5$, with size $2$;
• The subtree of base station $1$ contains all $6$ base stations.

Therefore, the stable base stations are $1,2,3$.

There are $6$ safe paths in total: $1 \to 2$, $1 \to 3$, $2 \to 1$, $3 \to 1$, $2 \to 3$, $3 \to 2$.

All base stations on these paths are stable base stations, so they meet the requirement.

Constraints

For $40\%$ of the testdata, it is guaranteed that $n \le 500$.

For all testdata, it is guaranteed that $1 \le n \le 500000$.

Translated by ChatGPT 5