Yet another tree problem

You are given a tree, that is, an undirected, connected graph with no cycles. You may choose any starting vertex, move around the tree step by step (from the current vertex to any adjacent vertex), visit every vertex at least once, and end your travel anywhere. What is the minimum number of steps to do so?

Input

Input consists of several cases, each with the number $n$ of vertices of the tree, followed by $n - 1$ pairs $x$ $y$ denoting an edge between $x$ and $y$ . Assume $2 \le n \le 10^5$ , that vertices are numbered between 1 and $n$ , and that the given edges indeed form a tree.

Output

For every graph, print the minimum number of steps to visit the whole tree.

Problem information

Author: Manuel Torres
Event: Vint-i-quatrè Concurs de Programació de la UPC - Semifinal
Date: 2026-06-18

Generation: 2026-06-10T22:55:34.453Z