Hotels

Time limit3sMemory limit256 MB

Summary

Count triplets of distinct towns in a tree whose three pairwise distances are all equal.

Level: Medium7 of 10
Topics: Tree, Dynamic programming, Combinatorics
Solved: No attempts yet

Problem

Byteotia has $n$ towns connected by $n-1$ roads of equal length. The roads form a tree.

The king wants three luxury hotels in three different towns, all at the same pairwise distance. Count how many such triplets exist.

Input

The first line contains $n$ ( $1 \le n \le 5000$ ). Each of the next $n-1$ lines contains two integers $a$ and $b$ ( $1 \le a \le b \le n$ ), the endpoints of a road.

Output

Print the number of valid hotel triplets.

Examples6

Example 1
Input
```
7
1 2
5 7
2 5
2 3
5 6
4 5
```
Expected output
```
5
```
Example 2
Input
```
3
1 2
2 3
```
Expected output
```
0
```
Example 3
Input
```
4
1 2
2 3
3 4
```
Expected output
```
0
```
Example 4
Input
```
5
1 2
1 3
1 4
1 5
```
Expected output
```
4
```
Example 5
Input
```
6
1 2
2 3
2 4
4 5
4 6
```
Expected output
```
2
```
Example 6
Input
```
1
```
Expected output
```
0
```