Dans la pelouse du parc KOI se trouve une fourmilière où vivent de nombreuses fourmis. Elle comprend $N$ chambres et $N-1$ passages reliant directement des chambres distinctes, et l’on peut aller de toute chambre à toute autre par les passages. La fourmilière est donc un arbre à $N$ sommets. Chaque chambre est numérotée de $1$ à $N$.

Chaque chambre peut accueillir au plus une fourmi. Si les chambres de deux fourmis sont directement reliées par un passage, elles se sentent mal à l’aise l’une avec l’autre. Ainsi, actuellement, au plus une des deux chambres reliées par chaque passage est occupée.

Les fourmis sont intelligentes : le nombre de fourmis qui habitent actuellement la fourmilière est donc aussi grand que possible sous cette condition. Autrement dit, si une fourmi supplémentaire arrivait, aucune répartition des fourmis dans les chambres ne pourrait respecter la condition.

Par une belle journée d’été, beaucoup de gens pique-niquent au parc KOI. Pendant qu’ils profitent de la pelouse, la terre de la fourmilière s’effrite et exactement un nouveau passage apparaît entre deux chambres distinctes. Ces chambres peuvent déjà être directement reliées. Autrement dit, pour tous entiers $1 \le i < j \le N$, un nouveau passage entre les chambres $i$ et $j$ peut apparaître, qu’il en existe déjà un ou non.

Ce passage peut relier directement les chambres de deux fourmis, rendant cette paire mal à l’aise. Les habitantes actuelles peuvent donc devoir se répartir autrement pour respecter la condition. Selon le choix de $(i,j)$, cela peut être possible, mais parfois aucune nouvelle répartition de toutes les fourmis actuelles ne respecte la condition. Dans ce cas, certaines habitantes peuvent devoir être expulsées.

Pour deux entiers $1 \le i < j \le N$, on appelle $(i,j)$ une paire pacifique si, après l’ajout d’un passage entre les chambres $i$ et $j$, toutes les fourmis peuvent respecter la condition par une répartition appropriée sans expulser personne. Étant donnée la structure de la fourmilière, comptez les paires pacifiques.

Contraintes

• $2 \le N \le 250\,000$
• $u \ne v$, $1 \le u,v \le N$
• La fourmilière donnée a une structure d’arbre.

Sous-tâches

1. (8 points) $N \le 16$.
2. (6 points) $N \le 80$.
3. (18 points) $N \le 400$.
4. (18 points) $N \le 2000$.
5. (6 points) $N \le 10000$.
6. (8 points) $N \le 50000$.
7. (36 points) Aucune contrainte supplémentaire.

Entrée

La première ligne contient $N$.

Chacune des $N-1$ lignes suivantes contient les numéros $u$ et $v$ des deux chambres reliées par un passage.

Sortie

Affichez le nombre de paires pacifiques sur la première ligne.

Exemples

Entrée 1

4
1 2
1 3
1 4

Sortie 1

3

Remarque

Initialement, au plus 3 fourmis peuvent vivre dans la fourmilière, et la seule répartition pour ce nombre est $\{2,3,4\}$. Ajouter un passage entre des chambres déjà directement reliées ne nécessite aucun changement. Il y a 3 cas de ce type. Dans tous les autres cas, aucune répartition ne peut accueillir 3 fourmis après l’ajout du passage.

Entrée 2

6
1 2
2 3
3 4
4 5
5 6

Sortie 2

15

Remarque

Initialement, au plus 3 fourmis peuvent vivre dans la fourmilière ; une répartition possible est $\{1,3,6\}$. Quel que soit le passage ajouté, il existe une répartition accueillant 3 fourmis.

Entrée 3

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

Sortie 3

11