Tree Matching

Solução escrita por Enzo Dantas e Caique Paiva

Um emparelhamento é um conjunto de arestas onde cada vértice tem grau 1 ou 0. Dada uma árvore com $n$ vértices, qual é o maior número de arestas em um emparelhamento?

Input

A primeira linha tem um inteiro $n$: O número de vértices. Os vértices são numerados em $1, 2, 3, \cdots, n$.

Então, temos $n-1$ linhas descrevendo as arestas. Cada linha tem dois inteiros $a, b$: tem uma aresta de $a$ para $b$.

Output

Imprima um inteiro: a quantidade máxima de pares.

Constantes

$1 \le n \le 2 \cdot 10^5$

$1 \le a, b \le n$

5
1 2
1 3
3 4
3 5

2

Explicação: O maior emparelhamento possível é $(1, 2)$ e $(3, 4)$.

(Link para submeter o problema).