题目描述

有一棵 $n$ 个结点的树，给每个点安排一个正整数编号，使得相邻点具有不同的编号，编号的总和尽量小。

输入格式

第一行一个整数 $n$。

以下 $n-1$ 行，每行两个数 $u,v(1\le u,v\le n)$，表示 $u$ 和 $v$ 间有一条边。

输出格式

仅一行，为最小编号和。

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

11

提示

对于 $20\%$ 的数据，$n\le 10$；

对于 $40\%$ 的数据，$n\le 1000$；

对于 $100\%$ 的数据，$1\le n\le 50000$。