KOI 公園的草坪上有一個許多螞蟻共同生活的蟻巢。蟻巢由 $N$ 個房間組成，有 $N-1$ 條通道直接連接不同房間，任意兩個不同房間之間都可以經過通道到達。也就是說，蟻巢是一棵有 $N$ 個頂點的樹。每個房間的編號為 $1$ 至 $N$。

蟻巢的每個房間最多能住一隻螞蟻。如果兩隻螞蟻所在的房間被通道直接連接，牠們就會彼此感到不舒服。因此，目前每條通道連接的兩個房間中，最多只有一個住著螞蟻。

螞蟻們很聰明，因此在滿足這一條件的前提下，目前蟻巢中居住的螞蟻數量已經盡可能多。換言之，如果再來一隻螞蟻，那麼無論怎樣安排所有螞蟻的房間，都無法滿足上述條件。

在一個晴朗的夏日，許多人來到 KOI 公園野餐。人們在草坪上野餐時，構成蟻巢的土壤會崩塌，從而恰好新增一條連接兩個不同房間的通道。這兩個房間原先也可能已有通道直接連接。換言之，對於任意兩個整數 $1 \le i < j \le N$，都可能新增一條連接房間 $i$ 和房間 $j$ 的通道，無論此前是否已有連接它們的通道。

新增通道可能直接連接兩隻螞蟻居住的房間，使這對螞蟻感到不舒服。因此，目前住在蟻巢裡的螞蟻可能需要重新安排位置，以滿足條件。根據 $(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 分) 無額外限制。

輸入格式

第一行給出 $N$。

接下來的 $N-1$ 行，每行給出一條通道連接的兩個房間的編號 $u$ 和 $v$。

輸出格式

第一行輸出和平對的數量。

範例

輸入格式 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