题目描述

在Byteotia有一个洞穴. 它包含n 个洞室和一些隧道连接他们. 每个洞室之间只有一条唯一的路径连接他们. Hansel 在其中一个洞室藏了宝藏, 但是它不会说出它在哪. Gretel 想知道. 当她询问一个洞室是否有宝藏时,如果她猜对了Hansel 会告诉她,如果猜错了他会告诉她哪个方向会有宝藏. 给出洞穴的信息,那么无论Hansel 把宝藏藏在了哪,求出最少要询问多少次才能找到宝藏.

输入格式

输入一个数n, 1<= n <= 50,000. 表示洞室总数,接下来n-1 行描述n – 1条边.

输出格式

输出一个数表示最少询问次数.

5
1 2
2 3
4 3
5 3

2

提示

没有写明提示

题目来源

Stage 2