Na trawniku parku KOI znajduje się mrowisko zamieszkane przez wiele mrówek. Składa się z $N$ komór i $N-1$ korytarzy bezpośrednio łączących różne komory. Między dowolnymi dwiema różnymi komorami można przejść korytarzami. Mrowisko jest więc drzewem o $N$ wierzchołkach. Komory są ponumerowane od $1$ do $N$.

W każdej komorze może mieszkać co najwyżej jedna mrówka. Jeśli komory dwóch mrówek są bezpośrednio połączone korytarzem, obie czują się niekomfortowo. Dlatego obecnie co najwyżej jedna z dwóch komór połączonych każdym korytarzem jest zamieszkana.

Mrówki są sprytne, więc obecnie mieszka ich w mrowisku możliwie najwięcej przy zachowaniu tego warunku. Innymi słowy, gdyby dołączyła jeszcze jedna mrówka, żadne rozmieszczenie wszystkich mrówek w komorach nie spełniałoby warunku.

W słoneczny letni dzień wielu ludzi urządza piknik w parku KOI. Podczas pikniku na trawniku ziemia tworząca mrowisko kruszy się i powstaje dokładnie jeden nowy korytarz między dwiema różnymi komorami. Mogą to być komory już bezpośrednio połączone. Innymi słowy, dla dowolnych liczb całkowitych $1 \le i < j \le N$ może powstać nowy korytarz między komorami $i$ i $j$, niezależnie od tego, czy wcześniej taki korytarz istniał.

Nowy korytarz może bezpośrednio połączyć komory dwóch mrówek, powodując ich dyskomfort. Obecne mieszkanki mogą więc musieć zmienić rozmieszczenie, aby spełnić warunek. Zależnie od wyboru $(i,j)$ bywa to możliwe, ale czasem żadne nowe rozmieszczenie wszystkich obecnych mrówek nie spełnia warunku. Wtedy niektóre mieszkanki mogą zostać wyproszone.

Dla liczb całkowitych $1 \le i < j \le N$ parę $(i,j)$ nazywamy pokojową, jeśli po dodaniu korytarza między komorami $i$ i $j$ mrówki mogą spełnić warunek przez odpowiednie przemieszczenie, bez wypraszania żadnej z nich. Mając strukturę mrowiska, policz pokojowe pary.

Ograniczenia

• $2 \le N \le 250\,000$
• $u \ne v$, $1 \le u,v \le N$
• Dane mrowisko ma strukturę drzewa.

Podzadania

1. (8 punktów) $N \le 16$.
2. (6 punktów) $N \le 80$.
3. (18 punktów) $N \le 400$.
4. (18 punktów) $N \le 2000$.
5. (6 punktów) $N \le 10000$.
6. (8 punktów) $N \le 50000$.
7. (36 punktów) Brak dodatkowych ograniczeń.

Wejście

Pierwszy wiersz zawiera $N$.

Każdy z kolejnych $N-1$ wierszy zawiera numery $u$ i $v$ komór połączonych jednym korytarzem.

Wyjście

Wypisz liczbę pokojowych par w pierwszym wierszu.

Przykład

Wejście 1

4
1 2
1 3
1 4

Wyjście 1

3

Uwagi

Początkowo mogą mieszkać najwyżej 3 mrówki, a jedynym rozmieszczeniem dla tej liczby jest $\{2,3,4\}$. Dodanie korytarza między już bezpośrednio połączonymi komorami nie wymaga zmian. Są 3 takie przypadki. W każdym innym przypadku po dodaniu korytarza nie istnieje rozmieszczenie dla 3 mrówek.

Wejście 2

6
1 2
2 3
3 4
4 5
5 6

Wyjście 2

15

Uwagi

Początkowo mogą mieszkać najwyżej 3 mrówki, a jednym z rozmieszczeń jest $\{1,3,6\}$. Niezależnie od dodanego korytarza istnieje rozmieszczenie dla 3 mrówek.

Wejście 3

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

Wyjście 3

11