You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

帝国的历史，如同滚滚的长河，带来一切，也会带走一切…

看到这道题的你，需要和界外魔来进行一场交易了。

题目描述

(PS:下文所指的子树均为图论意义上的子图，而非树父子关系上的子树)

界外魔似乎好几千岁了。当你提出想要掌握不老亡灵的法术时，他便向你提出了一个困扰他千年的问题。若你能给出解答，他便会赐予你通往虚空的能力。

界外魔首先画了一棵树给你：$n$ 个点，$n-1$ 条边，每个点分配了一个序号 $\rm Id$。

界外魔认为，生命集 $(x,y)$ 代表树上 $\mathrm{Id} \in [x,y]$ 的点的集合。而对于一个生命集，可以生成很多不同的生命树 $s_i(x,y)$。 具体要求如下：

1. 生命树一定是原树的一棵连通子树。
2. 生命树上的点一定包含生命集 $(x,y)$ 内的所有点。
3. 生命树可能包含 其他的点 和 任意数目的边 。

设 $\mathrm S(x,y) = \{s_i(x,y)\}_{\forall i}$，即生命集 $(x,y)$ 能够生成的所有生命树的集合。同时令函数 $\bold E(~ \mathrm S(x,y)~)$ 表示该集合内边数最少的那棵生命树的边数。那么界外魔希望你告诉 ta 下面式子的值：

输入格式

第 $1$ 行，一个整数 $n$ 表示点数。

第 $2\sim n$ 行，每行两个整数 $u,v$ 表示节点 $u$ 到节点 $v$ 有一条边。

输出格式

一行一个整数，表示答案，意义见题目描述。

样例 1

输入样例 1

4
1 4
1 3
2 4

输出样例 1

16

样例 2

输入样例 2

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

输出样例 2

240

数据规模与约定

对于前 $10\%$ 的数据，$n \le 10$。

对于前 $30\%$ 的数据，$n \le 5000$。

对于前 $60\%$ 的数据，$n \le 5\times 10^4$。

对于全部 $100\%$ 的数据，$n \le 3\times 10^5$，树的形态均匀随机。