Background

There is a cave in Byteotia.

Problem Description

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.

Input Format

The input contains an integer $n$, representing the total number of chambers.

The next $n-1$ lines describe $n-1$ edges.

Output Format

Output one integer representing the minimum number of questions.

5
1 2
2 3
4 3
5 3

2

Hint

For $100\%$ of the testdata, $1 \le n \le 50000$.

Translated by ChatGPT 5