P5912 [POI 2004] JAS

There is a cave in Byteotia.

It contains $n$ chambers and some tunnels connecting them. Between any two chambers, there is exactly one unique path connecting them. Hansel hid a treasure in one of the chambers, but he will not say where it is. Gretel knows that when she asks whether a certain chamber contains the treasure, if she guesses correctly Hansel will tell her so; if she guesses wrong, he will tell her in which direction the treasure lies. Given the information about the cave, no matter where Hansel hides the treasure, find the minimum number of questions needed to guarantee finding the treasure.

The input contains an integer $n$, representing the total number of chambers. The next $n-1$ lines describe $n-1$ edges.

Output one integer representing the minimum number of questions.

For $100\%$ of the testdata, $1 \le n \le 50000$. Translated by ChatGPT 5