[POI2004] JAS
题目背景
在 Byteotia 有一个洞穴。
题目描述
它包含 $n$ 个洞室和一些隧道连接他们。
每个洞室之间只有一条唯一的路径连接他们。Hansel 在其中一个洞室藏了宝藏,但是它不会说出它在哪。Gretel 知道,当她询问一个洞室是否有宝藏时,如果她猜对了 Hansel 会告诉她,如果猜错了他会告诉她哪个方向会有宝藏。 给出洞穴的信息,那么无论 Hansel 把宝藏藏在了哪,求出最少要询问多少次才能找到宝藏。
输入输出格式
输入格式
输入一个数 $n$,表示洞室总数。
接下来 $n-1$ 行描述 $n-1$ 条边。
输出格式
输出一个数表示最少询问次数。
输入输出样例
输入样例 #1
5
1 2
2 3
4 3
5 3
输出样例 #1
2
说明
对于 $100\%$ 的数据,$1\le n\le50000$。