En el césped del parque KOI hay un hormiguero donde viven muchas hormigas. Consta de $N$ cámaras y $N-1$ pasadizos que conectan directamente cámaras distintas, y se puede viajar entre cualesquiera dos cámaras distintas por los pasadizos. Es decir, el hormiguero es un árbol de $N$ vértices. Las cámaras se numeran de $1$ a $N$.

Cada cámara puede alojar como máximo una hormiga. Si las cámaras de dos hormigas están conectadas directamente por un pasadizo, ambas se sienten incómodas. Por tanto, actualmente, como máximo una de las dos cámaras conectadas por cada pasadizo está ocupada.

Las hormigas son inteligentes, por lo que actualmente vive el máximo número posible de hormigas que cumple esta condición. En otras palabras, si entrara una hormiga más, ninguna distribución de las hormigas en las cámaras podría cumplirla.

En un soleado día de verano, muchas personas van de pícnic al parque KOI. Al disfrutar del césped, la tierra del hormiguero se desmorona y aparece exactamente un nuevo pasadizo entre dos cámaras distintas. Estas cámaras podrían estar ya conectadas directamente. Es decir, para cualesquiera enteros $1 \le i < j \le N$, puede aparecer un nuevo pasadizo entre las cámaras $i$ y $j$, independientemente de que ya existiera uno.

Este pasadizo puede conectar directamente las cámaras de dos hormigas, haciendo que se sientan incómodas. Así, las hormigas actuales podrían tener que redistribuirse para cumplir la condición. Según la elección de $(i,j)$, esto puede ser posible, pero en algunos casos ninguna redistribución de todas las hormigas actuales cumple la condición. En esos casos, podría ser necesario expulsar a algunas.

Para dos enteros $1 \le i < j \le N$, llamamos pareja pacífica a $(i,j)$ si, al añadir un pasadizo entre las cámaras $i$ y $j$, las hormigas pueden cumplir la condición mediante una redistribución adecuada sin expulsar a ninguna. Dada la estructura del hormiguero, cuenta las parejas pacíficas.

Restricciones

• $2 \le N \le 250\,000$
• $u \ne v$, $1 \le u,v \le N$
• El hormiguero dado tiene estructura de árbol.

Subtareas

1. (8 puntos) $N \le 16$.
2. (6 puntos) $N \le 80$.
3. (18 puntos) $N \le 400$.
4. (18 puntos) $N \le 2000$.
5. (6 puntos) $N \le 10000$.
6. (8 puntos) $N \le 50000$.
7. (36 puntos) Sin restricciones adicionales.

Entrada

La primera línea contiene $N$.

Cada una de las siguientes $N-1$ líneas contiene los números $u$ y $v$ de las cámaras conectadas por un pasadizo.

Salida

Imprime la cantidad de parejas pacíficas en la primera línea.

Ejemplos

Entrada 1

4
1 2
1 3
1 4

Salida 1

3

Nota

Inicialmente pueden vivir como máximo 3 hormigas, y la única distribución con esa cantidad es $\{2,3,4\}$. Añadir un pasadizo entre cámaras ya conectadas directamente no exige cambiar la distribución. Hay 3 casos así. En cualquier otro caso, no existe ninguna distribución que aloje 3 hormigas tras añadir el pasadizo.

Entrada 2

6
1 2
2 3
3 4
4 5
5 6

Salida 2

15

Nota

Inicialmente pueden vivir como máximo 3 hormigas, y una distribución posible es $\{1,3,6\}$. Sea cual sea el pasadizo añadido, existe una distribución que aloja 3 hormigas.

Entrada 3

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

Salida 3

11