Gem-Toys 公司请你解决以下问题。

给你一个连通的无环图，即一个由边连接的顶点集合，使得从每个顶点出发都可以通过边到达所有其他顶点，且图中不包含环。

Gem-Toys 公司打算制作这种图的珠宝模型。顶点将由宝石制成，边将由金线制成。要求相邻的顶点必须由不同种类的宝石制成。对于每个正整数 $p$，恰好有一种价格为 $p$ 的宝石。

你的任务是编写一个程序，计算制作该模型所需的宝石的最小总价格。

输入格式

输入的第一行包含一个正整数 $N$ ($1 \le N \le 10\,000$)，表示顶点的数量。顶点从 $1$ 到 $N$ 进行编号。

接下来的 $N-1$ 行描述这些边，每行一条。这些行中的每一行都包含一对由空格隔开的整数 $A$ 和 $B$ ($1 \le A, B \le N, A \ne B$)。这样的一对数表示连接顶点 $A$ 和 $B$ 的一条边。

输出格式

输出的唯一一行包含一个整数：制作该模型所需的宝石的最小总价格。

样例

输入样例 1

8
1 2
3 1
1 4
5 6
1 5
5 7
5 8

输出样例 1

11