2071 - [POI2004]JAS

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

Input

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

Output

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

Examples

Input

5
1 2
2 3
4 3
5 3

Output

2
Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题