Problem Statement

Given is a tree with $N$ vertices. The vertices are numbered $1$ through $N$, and the $i$-th edge connects Vertex $A_i$ and Vertex $B_i$.

Find the number of pairs of integers $(x,y)$ that satisfy the following conditions.

• $0 \leq x \leq N$.
• There is a way to choose exactly $x$ vertices from the tree so that the sum of their degrees equals $y$.

Constraints

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq A_i < B_i \leq N$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer.