题目描述

有 $N$ 个城市和 $N-1$ 条双向道路，所有城市组成一棵树。开始时，只有城市 $1$ 拥有一份文件。

每天只能选择一个城市执行下面一种操作：

• 抄写文件：将该城市现有的文件数量变为原来的两倍。
• 传递文件：将该城市的一份文件沿一条道路传给相邻城市，该城市的文件数量减少一份，相邻城市的文件数量增加一份。

请计算使每个城市都至少拥有一份文件所需的最少天数。

输入格式

第一行包含一个整数 $N$。

接下来 $N-1$ 行，每行包含两个整数 $U_i,V_i$，表示城市 $U_i$ 和城市 $V_i$ 之间有一条双向道路。

输出格式

输出一个整数，表示所需的最少天数。

样例

3
1 2
1 3

4

数据范围与提示

• $1 \le N \le 10^5$
• $1 \le U_i,V_i \le N$，且 $U_i \ne V_i$
• 输入的道路保证构成一棵树