Contexto do Problema

Este problema foi adaptado da competição CERC 2019. Trata-se de determinar o número mínimo de operações necessárias para converter uma estrutura de anéis conectados, chamada de cadeia incompleta, em uma cadeia reta, onde cada anel está conectado a no máximo dois outros.

Descrição do Problema

Uma cadeia incompleta é representada como um grafo conexo com N anéis (nós) e N-1 conexões (arestas). Bob, um aprendiz de ferreiro, construiu essa estrutura seguindo uma regra: começar com um único anel e, para cada novo anel, conectá-lo a um anel existente na estrutura. O resultado é uma árvore (grafo acíclico conexo).

Para obter uma cadeia reta (um caminho simples onde cada nó tem grau no máximo 2), Bob pode realizar operações. Em cada operação, ele escolhe um anel A conectado a outro anel B. Ele então desconecta A de B e o reconecta a um terceiro anel C (que pode ser qualquer um, exceto B). Se A estava conectado a outros anéis além de B, essas conexões são mantidas.

O objetivo é calcular o número mínimo dessas operações necessárias para transformar a cadeia incompleta em uma cadeia reta.

Formato de Entrada

A entrada consiste em:

• A primeira linha contém um inteiro N (1 ≤ N ≤ 3 × 10^5), representando o número de anéis.
• As próximas N-1 linhas cada uma contém dois inteirso u e v, indicando que os anéis u e v estão conectados. As numerações dos anéis vão de 1 a N.

A estrutura garante que o grafo é conexo (existe um caminho entre qualquer par de anéis).

Formato de Saída

Imprima um único inteiro representando o número mínimo de operações necessárias.

Exemplos

Exemplo 1:

Entrada:

5
4 3
1 2
4 5
3 2

Saída:

0

Explicação: A cadeia já é uma cadeia reta (um caminho simples: 1-2-3-4-5), então nenhuma operação é necessária.

Exemplo 2:

Entrada:

6
1 3
3 2
3 4
4 5
4 6

Saída:

2

Explicação: A estrutura é uma árvore com ramificações. São necessárias duas operações para desconectar ramos e linearizar a cadeia.

Exemplo 3:

Entrada:

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

Saída:

1

Explicação: A estrutura tem um ramo (6-7) que precisa ser reconectado. Uma operação é suficiente.

Observações Técnicas

O problema pode ser modelado como otimização em árvores. A solução envolve analisar a estrutura da árvore para identificar nós com grau maior que 2 e calcular as operações mínimas para reduzir esses graus, mantendo a conectividade.