题目描述

在 HF 有 $n$ 个城镇，通过 $n-1$ 条道路连接。每条道路直接连接两个城镇。所有的道路长度相同，并且是双向的。

已知每个城镇都可以通过一条或多条（直接连接的）道路到达其他城镇。换句话说，道路网络形成了一棵树。

HF 的国王 LXX 希望建造三家豪华酒店，以吸引来自世界各地的游客。国王希望这些酒店位于不同的城镇，并且它们彼此之间的距离相同。

请通过编写程序来帮助国王，确定在 HF 中可能的酒店三元组位置的数量。

输入格式

第一行包含一个整数 $n$，表示 HF 中的城镇数量。城镇编号从 $1$ 到 $n$。

接下来 $n-1$ 行描述了 HF 的道路网络。每行包含两个整数 $a$ 和 $b$，用一个空格分隔，表示在城镇 $a$ 和 $b$ 之间有一条直接的道路。

输出格式

输出一行一个整数，表示可能的酒店位置三元组的数量。

样例输入 1

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

样例输出 1

5

说明

其它样例说明

• 样例 $2$：见选手目录下的 hotel/hotel2.in 与 hotel/hotel2.ans，该测试用例满足测试点编号 $1\sim 5$ 的约束条件。
• 样例 $3$：见选手目录下的 hotel/hotel3.in 与 hotel/hotel3.ans，该测试用例满足测试点编号 $6\sim 10$ 的约束条件。
• 样例 $4$：见选手目录下的 hotel/hotel4.in 与 hotel/hotel4.ans，该测试用例满足测试点编号 $11\sim 15$ 的约束条件。
• 样例 $5$：见选手目录下的 hotel/hotel5.in 与 hotel/hotel5.ans，该测试用例满足测试点编号 $16\sim 17$ 的约束条件。
• 样例 $6$：见选手目录下的 hotel/hotel6.in 与 hotel/hotel6.ans，该测试用例满足测试点编号 $18\sim 20$ 的约束条件。

数据范围

• $1 \le n \le 5000$
• 输入保证是一棵树

各测试点的限制如下表所示：

点击下载大样例