KOI 公園の芝生には、多くのアリが暮らす巣があります。巣は $N$ 個の部屋と、異なる部屋を直接結ぶ $N-1$ 本の通路からなり、任意の異なる 2 部屋の間を通路で移動できます。つまり、巣は $N$ 頂点の木です。各部屋には $1$ から $N$ の番号が付いています。

各部屋には高々 1 匹のアリが住めます。2 匹のアリが住む部屋が通路で直接結ばれていると、その 2 匹は互いに居心地が悪くなります。そのため、現在は各通路が結ぶ 2 部屋のうち、高々一方にだけアリが住んでいます。

アリは賢いので、この条件を満たしつつ、現在の巣には可能な限り多くのアリが住んでいます。つまり、もう 1 匹増えると、部屋にどのように配置しても条件を満たせません。

晴れた夏の日、KOI 公園には多くの人がピクニックに訪れます。芝生で楽しんでいるうちに巣の土が崩れ、異なる 2 部屋を結ぶ通路がちょうど 1 本新しくできます。この 2 部屋はすでに直接結ばれている場合もあります。つまり、任意の整数 $1 \le i < j \le N$ に対し、以前にその通路があったかに関係なく、部屋 $i$ と $j$ を結ぶ通路が追加され得ます。

新しい通路により 2 匹のアリが住む部屋が直接結ばれ、居心地の悪い組ができるかもしれません。そのため、現在住んでいるアリは条件を満たすよう配置を変える必要があるかもしれません。$(i,j)$ の選び方によっては可能ですが、どのように配置を変えても条件を満たせない場合もあります。その場合、住んでいたアリを追い出さなければならないかもしれません。

整数 $1 \le i < j \le N$ に対し、部屋 $i$ と $j$ を結ぶ通路が追加されたとき、誰も追い出さずに適切な再配置で条件を満たせるなら、$(i,j)$ を平和な組と呼びます。巣の構造が与えられたとき、平和な組の個数を数えてください。

制約

• $2 \le N \le 250\,000$
• $u \ne v$, $1 \le u,v \le N$
• 与えられる巣は木構造です。

小課題

1. (8 点) $N \le 16$.
2. (6 点) $N \le 80$.
3. (18 点) $N \le 400$.
4. (18 点) $N \le 2000$.
5. (6 点) $N \le 10000$.
6. (8 点) $N \le 50000$.
7. (36 点) 追加の制約はありません。

入力

1 行目に $N$ が与えられます。

続く $N-1$ 行には、各通路が結ぶ 2 部屋の番号 $u$ と $v$ が与えられます。

出力

1 行目に平和な組の個数を出力してください。

入出力例

入力 1

4
1 2
1 3
1 4

出力 1

3

注記

最初は最大 3 匹が住むことができ、そのときの配置は $\{2,3,4\}$ だけです。すでに直接結ばれている部屋の間に通路が追加されても、配置を変える必要はありません。このような場合は 3 通りです。それ以外では、どの通路が追加されても 3 匹が住める配置は存在しません。

入力 2

6
1 2
2 3
3 4
4 5
5 6

出力 2

15

注記

最初は最大 3 匹が住むことができ、そのときの配置の一例は $\{1,3,6\}$ です。どの通路が追加されても、3 匹が住める配置が存在します。

入力 3

7
1 2
1 3
2 4
2 5
3 6
3 7

出力 3

11