Descripción

¡El Casique Guaso se presenta a presidente de Guantánamo! En los debates, se le preguntará cómo resolver el problema de transporte de Guantanamo. Es un problema realmente difícil porque el sistema de transporte de Guantanamo es ahora un árbol (grafo conectado sin ciclos). El equipo de Guaso ha descubierto en el Ministerio de Transporte de Guantanamo que sólo hay dinero en el presupuesto para una carretera adicional. En los debates, va a decir que construirá esta carretera como forma de maximizar el número de caminos simples distintos en el país. Un camino simple es un camino que no pasa más de una vez por cada vértice. Dos caminos simples se denominan distintos si los conjuntos de sus aristas son distintos.

Pero la ciencia de Guantanamo está deteriorada, por lo que el equipo de Guaso no ha conseguido encontrar a ningún científico que responda cuántos caminos simples distintos pueden conseguir tras añadir exactamente una arista en el sistema de transporte.

Ayuda a Guaso a resolverlo.

Se puede añadir una arista entre vértices que ya están conectados, pero no puede ser un bucle.

En este problema, consideramos sólo caminos simples de longitud al menos dos.

Entrada

La primera línea contiene un número entero ~n~ (~2 \le n \le 500 000~) - número de vértices en el sistema de transporte de Guantanamo.

Cada una de las siguientes ~n-1~ líneas contiene dos enteros ~v_i~ y ~u_i~ (~1 \le v_i, u_i \le n~). Se garantiza que el grafo es arborescente.

Salida

Imprime exactamente un entero - número máximo de caminos simples que se pueden conseguir después de añadir una arista.

Ejemplos

Entrada 1

2          
1 2

Salida 1

2

Entrada 2

4         
1 2
1 3
1 4

Salida 2

11

Entrada 3

6      
1 2
1 3
3 4
3 5
4 6

Salida 3

29