問題文

$N$ 頂点からなる木が与えられます． 頂点には $1$ から $N$ までの番号がついており，$i$ 番目の辺は頂点 $A_i$ と頂点 $B_i$ を結んでいます．

整数の組 $(x,y)$ であって，以下の条件を満たすものが何通りあるかを求めてください．

• $0 \\leq x \\leq N$

• 木からちょうど $x$ 個の頂点を選び，その次数の和をちょうど $y$ にすることができる．

制約

• $2 \\leq N \\leq 2 \\times 10^5$
• $1 \\leq A_i < B_i \\leq N$
• 入力されるグラフは木である．

入力

入力は以下の形式で標準入力から与えられる．

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

出力

答えを出力せよ．

入力例 1

3
1 2
2 3

出力例 1

6

条件を満たす $(x,y)$ の組は以下の $6$ 通りです．

• $x=0,y=0$
• $x=1,y=1$
• $x=1,y=2$
• $x=2,y=2$
• $x=2,y=3$
• $x=3,y=4$

例えば，頂点 $1$ と頂点 $2$ を選ぶと次数の和が $3$ になるため，$x=2,y=3$ は条件を満たします．

入力例 2

5
1 2
2 3
2 4
4 5

出力例 2

16

入力例 3

10
2 9
8 10
2 10
4 6
5 6
1 8
2 7
3 6
6 8

出力例 3

65