[Baltic2003]Gem

给出一棵树，要求你为树上的结点标上权值，权值可以是任意的正整数。

唯一的限制条件是相邻的两个结点不能标上相同的权值。要求给出一种方案，使得整棵树的总权值最小。

输入格式

第一行一个数字 $N$，代表树上有 $N$ 个点。

接下来 $N-1$ 行，每行两个整数，代表这两个点相连。

输出格式

输出最小的总权值。

样例输入

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

样例输出

14

数据范围

• $N\le 10^4$。

来源与许可

本题为 Baltic 2003 试题「Gem」，题面与测试数据整理自 BZOJ 1369。

样例 1

输入

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

输出

14