当前没有测试数据。

题目描述

某个古老的王国有 $N$ 个城市，编号为 $1 … N$。这些城市通过 $N − 1$ 条双向道路连接，形成一个树形结构，其中 $1$ 号城市是首都。每个城市都可以从 $1$ 号城市出发通过若干条双向道路到达。

某天，$1$ 号城市准备将一条重要的公告文件中的信息，传递到王国中的的所有城市。

王国传递公告文件信息的过程，有一定的特殊性。具体来说，每天 $N$ 个城市中，只会有一个城市进行文件信息的传递工作，这个城市会做如下两种操作其中之一的工作。

• 抄写文件：如果当前城市中已有公告文件，该城市会将当前城市中公告文件的数量通过抄写翻倍。
• 文件传输：如果当前城市中有公告文件，该城市可以选择将其中一份公告文件从当前城市，沿双向道路传送到其他城市，该城市中公告文件的数量会少一份。

请帮助王国计算，每个城市都能获得至少一份公告文件，所需的最少天数。

输入格式

输入的第一行包含一个整数 $N$，表示城市的数量。

接下来的 $N − 1$ 行，每行包含两个整数 $U_i$ 和 $V_i$，表示服务器 $U_i$ 和 $V_i$ 之间有一条双向道路。

输出格式

输出一个整数，表示每个城市都能获得至少一份公告文件，所需的最少天数。

样例 #1

输入

3
1 2
1 3

输出

4

数据范围

对于 $25\%$ 的测试数据，满足 $2 \sim N$ 的每个城市直接与 $1$ 号城市相连。

对于另外 $20\%$ 的数据，满足 $2 \sim N$ 的每个城市，与该城市连接的双向道路最多有 $2$ 条。

对于 $100\%$ 的数据，满足 $1 \le N \le 10^5$，$1 \le U_i, V_i \le N$，$U_i \neq V_i$。