题目描述

给定一棵$n$个节点的树，节点编号为$1 \sim n$，每条边的长度均为1。你想要选取三个节点，使它们两两间距离相同，求总的方案数。不区分三个节点的顺序，即$\{1,2,3\}$与$\{2,1,3\}$是同一种方案。

输入格式

第一行一个正整数$n$；
接下来$n-1$行，每行两个整数$u,v$，表示点$u$与点$v$之间有一条边。输入保证是一棵树。

输出格式

一个非负整数，表示所求的方案数。

样例

输入

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

输出

5

样例说明

样例中的5种方案为$\{1,3,5\},\quad\{2,4,6\},\quad\{2,4,7\},\quad\{2,6,7\},\quad\{4,6,7\}$。

数据规模、时空限制

对于20%的数据，$n \le 50$
对于50%的数据，$n \le 500$
对于100%的数据，$n \le 5000$
时间限制1s，空间限制512MB。

来源

2019.2 TYWZ提高组集训
供题人：于剑