题目描述

给定一棵\(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提高组集训
供题人：于剑