Im Rasen des KOI-Parks liegt ein Ameisenbau, in dem viele Ameisen zusammenleben. Er besteht aus $N$ Kammern und $N-1$ Gängen, die verschiedene Kammern direkt verbinden. Zwischen beliebigen zwei verschiedenen Kammern kann man über Gänge gelangen. Der Bau ist also ein Baum mit $N$ Knoten. Jede Kammer trägt eine Nummer von $1$ bis $N$.

In jeder Kammer kann höchstens eine Ameise wohnen. Sind die Kammern zweier Ameisen direkt durch einen Gang verbunden, fühlen sich beide unwohl. Daher ist derzeit von den beiden durch einen Gang verbundenen Kammern höchstens eine bewohnt.

Die Ameisen sind klug, daher leben derzeit so viele Ameisen wie möglich im Bau, während diese Bedingung erfüllt bleibt. Würde also noch eine Ameise einziehen, könnte keine Anordnung aller Ameisen in den Kammern die Bedingung erfüllen.

An einem sonnigen Sommertag picknicken viele Menschen im KOI-Park. Dabei zerbröckelt die Erde des Ameisenbaus, und genau ein neuer Gang zwischen zwei verschiedenen Kammern entsteht. Die beiden Kammern können bereits direkt verbunden sein. Für beliebige ganze Zahlen $1 \le i < j \le N$ kann also ein neuer Gang zwischen den Kammern $i$ und $j$ entstehen, unabhängig davon, ob es vorher schon einen gab.

Der neue Gang kann zwei bewohnte Kammern direkt verbinden, wodurch sich dieses Ameisenpaar unwohl fühlt. Die bisherigen Bewohnerinnen müssen sich daher möglicherweise neu verteilen, um die Bedingung zu erfüllen. Je nach Wahl von $(i,j)$ ist das möglich, doch manchmal erfüllt keine neue Anordnung aller bisherigen Ameisen die Bedingung. Dann müssen möglicherweise einige Bewohnerinnen ausziehen.

Für ganze Zahlen $1 \le i < j \le N$ heißt $(i,j)$ ein friedliches Paar, wenn nach dem Hinzufügen eines Gangs zwischen den Kammern $i$ und $j$ alle Ameisen durch geeignete Neuverteilung die Bedingung erfüllen können, ohne eine Ameise zu vertreiben. Zähle für die gegebene Struktur des Baus die friedlichen Paare.

Beschränkungen

• $2 \le N \le 250\,000$
• $u \ne v$, $1 \le u,v \le N$
• Der gegebene Ameisenbau hat eine Baumstruktur.

Teilaufgaben

1. (8 Punkte) $N \le 16$.
2. (6 Punkte) $N \le 80$.
3. (18 Punkte) $N \le 400$.
4. (18 Punkte) $N \le 2000$.
5. (6 Punkte) $N \le 10000$.
6. (8 Punkte) $N \le 50000$.
7. (36 Punkte) Keine zusätzlichen Einschränkungen.

Eingabe

Die erste Zeile enthält $N$.

Jede der nächsten $N-1$ Zeilen enthält die Nummern $u$ und $v$ der durch einen Gang verbundenen Kammern.

Ausgabe

Gib in der ersten Zeile die Anzahl der friedlichen Paare aus.

Beispiele

Eingabe 1

4
1 2
1 3
1 4

Ausgabe 1

3

Hinweis

Anfangs können höchstens 3 Ameisen im Bau wohnen, und die einzige Anordnung für diese Anzahl ist $\{2,3,4\}$. Ein neuer Gang zwischen bereits direkt verbundenen Kammern erfordert keine Neuverteilung. Es gibt 3 solche Fälle. In jedem anderen Fall kann nach Hinzufügen des Gangs keine Anordnung 3 Ameisen beherbergen.

Eingabe 2

6
1 2
2 3
3 4
4 5
5 6

Ausgabe 2

15

Hinweis

Anfangs können höchstens 3 Ameisen im Bau wohnen; eine mögliche Anordnung ist $\{1,3,6\}$. Unabhängig vom hinzugefügten Gang gibt es eine Anordnung für 3 Ameisen.

Eingabe 3

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

Ausgabe 3

11