Byteotia 有 $n$ 个城镇，由 $n-1$ 条道路连接。每条道路直接连接两个城镇，所有道路长度相同且为双向。已知从任何一个城镇出发，都可以通过一条或多条（直接连接的）道路到达其他任何城镇。换句话说，道路网络构成了一棵树。

Byteotia 的国王 Byteasar 想要建造三家豪华酒店，以吸引来自世界各地的游客。国王希望这三家酒店位于不同的城镇，且它们两两之间的距离相等。

请编写一个程序，帮助国王计算在 Byteotia 中放置这三家酒店的可能位置组合数。

输入格式

输入的第一行包含一个整数 $n$ ($1 \le n \le 5\,000$)，表示 Byteotia 的城镇数量。城镇编号从 $1$ 到 $n$。

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

输出格式

输出的第一行也是唯一一行应包含一个整数，表示放置酒店的可能方案数。

样例

输入 1

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

输出 1

5

可以建造酒店的城镇三元组（无序）为：{1,3,5}, {2,4,6}, {2,4,7}, {2,6,7}, {4,6,7}。