题目描述

奶牛们正在玩电线！他们学会了焊接：把两条电线连接起来，将某条的端点焊接到另一条的中间某个位置(注意：不能够将两条电线的端点焊接起来，即中间某个位置不包括端点)。当然，中间的同一个位置可以焊接多条电线。(并且焊接点必须为整数点，这个好像英文题面没说，我是这么理解的)

奶牛们准备建造一个神奇的结构。它是一个$\red{N(1 <= N <= 50,000)}$个节点$\red{N-1}$条边的图，并且任意两个节点连通。每条边通过两个整数$\red{A,B}$来表示$\red{(1 <= A <=N}$; $\red{1 <= B <= N}$; $\red{A != B)}$。

奶牛们要从当地的店里买电线，然而，越长的电线就越贵，具体地：一条长度为$\red{L}$的电线的售价为$\red{L\times L，}$并且，电线是不允许连接或者裁断的。

给出奶牛准备建造的结构，请帮助奶牛们找出最小的花费。

输入格式

第一行: 一个整数 $\red{N}$

第二到$\red{N}$行: 每行两个整数$\red{A,B}$描述一条边

输出格式

第一行：一个整数表示最小的花费，注意这个整数可能超过$\red{32}$位二进制数。

样例

输入样例

6
1 2
1 3
1 4
1 5
1 6

输出样例

7

提示

输出详情:

由于每个节点都和$\red{1}$号节点相连，因此，我们只要购买$\red{1}$条长度为$\red{2}$的电线和$\red{3}$条长度为$\red{1}$的电线即可。

总的花费为$\red{2\times 2 +1\times 1 + 1\times 1 + 1\times 1 = 7}$。