No gramado do parque KOI há um formigueiro onde vivem muitas formigas. Ele consiste em $N$ câmaras e $N-1$ passagens que ligam diretamente câmaras distintas, e é possível ir entre quaisquer duas câmaras distintas pelas passagens. Ou seja, o formigueiro é uma árvore com $N$ vértices. As câmaras são numeradas de $1$ a $N$.

Cada câmara pode abrigar no máximo uma formiga. Se as câmaras de duas formigas estiverem diretamente ligadas por uma passagem, ambas ficam desconfortáveis. Portanto, atualmente, no máximo uma das duas câmaras ligadas por cada passagem está ocupada.

As formigas são inteligentes, então atualmente vive no formigueiro o maior número possível de formigas que respeita essa condição. Em outras palavras, se entrasse mais uma formiga, nenhuma distribuição das formigas nas câmaras poderia satisfazer a condição.

Em um dia ensolarado de verão, muitas pessoas fazem piqueniques no parque KOI. Enquanto aproveitam o gramado, a terra do formigueiro desmorona e surge exatamente uma nova passagem entre duas câmaras distintas. Essas câmaras já podem estar diretamente ligadas. Ou seja, para quaisquer inteiros $1 \le i < j \le N$, pode surgir uma nova passagem entre as câmaras $i$ e $j$, independentemente de já existir uma.

Essa passagem pode ligar diretamente câmaras ocupadas por duas formigas, deixando esse par desconfortável. As moradoras atuais podem, portanto, precisar se reorganizar para satisfazer a condição. Dependendo da escolha de $(i,j)$, isso pode ser possível, mas em alguns casos nenhuma reorganização de todas as formigas atuais satisfaz a condição. Nesses casos, algumas moradoras podem ter de ser expulsas.

Para dois inteiros $1 \le i < j \le N$, chamamos $(i,j)$ de par pacífico se, ao adicionar uma passagem entre as câmaras $i$ e $j$, todas as formigas puderem satisfazer a condição por uma reorganização adequada sem expulsar nenhuma. Dada a estrutura do formigueiro, conte os pares pacíficos.

Restrições

• $2 \le N \le 250\,000$
• $u \ne v$, $1 \le u,v \le N$
• O formigueiro dado tem estrutura de árvore.

Subtarefas

1. (8 pontos) $N \le 16$.
2. (6 pontos) $N \le 80$.
3. (18 pontos) $N \le 400$.
4. (18 pontos) $N \le 2000$.
5. (6 pontos) $N \le 10000$.
6. (8 pontos) $N \le 50000$.
7. (36 pontos) Sem restrições adicionais.

Entrada

A primeira linha contém $N$.

Cada uma das próximas $N-1$ linhas contém os números $u$ e $v$ das câmaras ligadas por uma passagem.

Saída

Imprima a quantidade de pares pacíficos na primeira linha.

Exemplos

Entrada 1

4
1 2
1 3
1 4

Saída 1

3

Nota

Inicialmente podem viver no máximo 3 formigas, e a única distribuição com essa quantidade é $\{2,3,4\}$. Adicionar uma passagem entre câmaras já diretamente ligadas não exige reorganização. Há 3 casos assim. Em qualquer outro caso, não existe distribuição que abrigue 3 formigas após a adição da passagem.

Entrada 2

6
1 2
2 3
3 4
4 5
5 6

Saída 2

15

Nota

Inicialmente podem viver no máximo 3 formigas, e uma distribuição possível é $\{1,3,6\}$. Qualquer que seja a passagem adicionada, existe uma distribuição que abriga 3 formigas.

Entrada 3

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

Saída 3

11