有一个城市网络，需要在某些城市放置广播站以广播相同的信息。每个广播站都有其自身的传输功率 $p$，使得它可以向距离 $p$ 以内的任何城市广播信息。这里，两个城市之间的距离是指它们之间（唯一）路径上所包含的边数。在本题中，城市网络是一棵具有 $n$ 个顶点的树 $T$，每个顶点代表一个城市。

对于一棵具有 $n$ 个顶点集合 $V$ 的树 $T$，我们将为每个顶点 $v \in V$ 分配一个非负整数 $p(v)$，称为广播功率，使得每个满足 $p(u) = 0$ 的顶点 $u$ 都在某个满足 $p(v) > 0$ 的顶点 $v$ 的距离 $p(v)$ 以内。此时，我们可以将满足 $p(v) > 0$ 的顶点 $v$ 视为传输功率为 $p(v)$ 的广播站，如果 $u$ 在 $v$ 的距离 $p(v)$ 以内，则顶点 $u$ 可以接收到 $v$ 的广播。

本题的目标是找到一种上述顶点 $v \in V$ 的广播功率 $p(v)$ 的分配方案，使得 $\sum_{v \in V} p(v)$ 最小。

例如，图 A.1 展示了两种广播功率的分配方案。在图 A.1 (a) 的情况下，只有顶点 6 的广播功率为 4，其他顶点的广播功率均为 0。那么所有广播功率为 0 的顶点都可以接收到顶点 6 的广播。在图 A.1 (b) 的情况下，顶点 3 和 9 的广播功率分别为 2 和 1。那么所有广播功率为 0 的顶点都可以接收到顶点 3 或 9 的广播。这种方案使得广播功率之和最小。

图 A.1：两种广播功率的分配方案

输入格式

程序从标准输入读取数据。第一行包含一个整数 $n$ ($1 \le n \le 5,000$)，表示输入树 $T$ 的顶点数。树 $T$ 的顶点编号为 $1$ 到 $n$。接下来的 $n - 1$ 行，每行包含两个整数 $a$ 和 $b$ ($1 \le a, b \le n$)，表示 $T$ 中连接顶点 $a$ 和 $b$ 的一条边。

输出格式

程序将结果写入标准输出。输出一行，包含一个整数，即上述树 $T$ 中各顶点广播功率所有可能分配方案中的最小广播功率之和。

样例

样例输入 1

6
1 2
3 2
2 4
5 4
6 4

样例输出 1

2

样例输入 2

12
1 2
2 3
4 5
5 3
3 6
6 7
7 8
8 9
12 9
9 11
10 9

样例输出 2

3