问题描述

有一天，一个珠宝商来找你，希望你帮他解决一个问题： 珠宝商手下的设计师最近交给他一种新型装饰品的设计图纸：一个无环的连通图。图中的每一个结点都代表了一颗宝石，结点间的边在成品中则表示连接这两个结点所对应宝石的金线。

为了不让饰品看上去过于单调，一根金线两头的宝石不能相同。珠宝店里有无限多种宝石，每种有无限多颗。第p种宝石的价钱是p元/颗（p为正整数）。

你的任务是，计算如果按照上述要求选取宝石，那么为了制作一个这样的饰品，被选出的宝石的总价最少是多少。

输入：

第一行是一个正整数n(1 <= n <= 10000)，表示图中的结点数。图中所有结点按1~n顺序编号。

接下来n-1行，每行包括两个正整数a、b（1 ≤ a, b ≤ n, a ≠ b），表示结点a与结点b之间有一条无向边。

输出：

输出一个数，即按要求选出宝石的最小总价。

样例gems.in

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

样例gems.out

11