Time Limit: 3000 MS    Memory Limit: 65536 K 


Description

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

Input

第一行:n(n<=50,000) 以下n-1行,每行两个数u,v(1<=u, v<=n),表示u和v有一条边

Output

仅一行,为最小编号和

Sample Input

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

Sample Output

11