UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#1369. [Baltic2003]Gem

Statistics 下载数据

Description

给出一棵树,要求你为树上的结点标上权值,权值可以是任意的正整数 唯一的限制条件是相临的两个结点不能标上相同的权值,要求一种方案,使得整棵树的总价值最小。

Input

先给出一个数字N,代表树上有N个点,N<=10000 下面N-1行,代表两个点相连

Output

最小的总权值

Sample Input

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

Sample Output

14

Hint

Source