C. 氙的攻击——帮派网络

单次测试时间限制：$3$ 秒
单次测试内存限制：$512$ 兆字节

---

在 A.R.C. Markland-N 的另一层楼，年轻的程序员西蒙·“氙”·杰克逊早早完成了他的项目（一如既往地提前）。闲来无事，他决定化身传奇黑客 “X”，与网络世界中的帮派展开对抗。

他的目标是包含 $n$ 个小帮派的网络。
该网络恰好有 $n-1$ 条直接链路，每条链路连接两个帮派。链路分布方式保证：任意两个帮派之间都存在唯一一条由若干条链路构成的简单路径。

通过数据挖掘，氙发现帮派使用了一种交叉加密方式以避免被查获：
每条链路被分配一个 $0$ 到 $n-2$ 之间 的整数，所有整数互不相同，且每个整数恰好被分配给某一条链路。
如果入侵者试图访问加密数据，他们必须突破 $S$ 层密码防护，其中 $S$ 的定义如下：

$$S = \sum_{1 \le u < v \le n} \mathrm{mex}(u, v)$$

这里，$\mathrm{mex}(u, v)$ 表示：在从帮派 $u$ 到帮派 $v$ 的唯一简单路径上的所有链路中，没有出现的最小非负整数。

氙并不知道整数是如何分配到链路上的，但这并不成问题。他打算让他的 AI 实例尝试所有可能的分配方式，但在此之前，他需要知道 $S$ 可能的最大值，以便高效部署 AI。

现在氙要编写 AI 脚本，预计两小时内完成。在他回来之前，你能找出最大的可能 $S$ 吗？

---

输入格式
第一行包含一个整数 $n$（$2 \le n \le 3000$），表示帮派数量。
接下来 $n-1$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，$u_i \ne v_i$），表示帮派 $u_i$ 和 $v_i$ 之间有一条直接链路。
数据保证链路分布使得任意两个帮派之间都有唯一一条简单路径相连。

---

输出格式
输出最大的可能值 $S$ —— 帮派网络中的密码防护层数。

---

样例

样例输入 1

3
1 2
2 3

样例输出 1

3

样例输入 2

5
1 2
1 3
1 4
3 5

样例输出 2

10

---

注释

在第一个样例中，可以通过如下分配达到最大 $S$：

按此分配，
$\mathrm{mex}(1,2) = 0$，$\mathrm{mex}(1,3) = 2$，$\mathrm{mex}(2,3) = 1$，
因此 $S = 0 + 2 + 1 = 3$。

在第二个样例中，可以通过如下分配达到最大 $S$：

按此分配，所有非零的 mex 值如下：
$\mathrm{mex}(1,3) = 1$，$\mathrm{mex}(1,5) = 2$，$\mathrm{mex}(2,3) = 1$，
$\mathrm{mex}(2,5) = 2$，$\mathrm{mex}(3,4) = 1$，$\mathrm{mex}(4,5) = 3$，
因此 $S = 1 + 2 + 1 + 2 + 1 + 3 = 10$。