Description

奶牛决定用电线焊接出一张图，这张图是连通的，由 $N$ 个点，$N-1$ 条边组成，每条边的长度都是 $1$。焊接所用的电线要从当地的商店里买。越长的电线越贵，一条长度为 $L$ 的电线售价为 $L^2$。奶牛们已经学会了基本的焊接方法，她们会把某条电线的一个端点焊接到另一条电线的中间某个位置，但她们没有学会如何把两条电线的端点直接焊接起来，也没有学会怎么把电线剪断。给定奶牛准备焊接的图，请告诉奶牛怎么焊接才能最节约材料费用。

Input Format

第 $1$ 行：一个整数 $N$。

第 $2 \sim N$ 行：描述边的两个以空格分隔的整数：$A$ 和 $B$。

Output Format

第 $1$ 行：一个整数，将树焊接在一起的成本。

请注意，此数字可能并不总是适合32位整数。

6 
1 2 
1 3 
1 4 
1 5 
1 6 

7 

Hint

由于结构中的所有节点都连接到节点 $1$，我们只需要购买一根长度为 $2$ 的电线和三根长度为 $1$ 的电线，总成本为 $2 * 2 + 1 * 1 + 1 * 1 + 1 * 1 = 7$。

对于至少 $50\%$ 的测试数据，有 $N \leq 2,000$。