Equidistant Triplets in a Tree

Given a tree with n vertices, count the number of unordered triplets (i, j, k) such that the distance between every pair of vertices among i, j, k is equal. In other words, find the number of triplets satisfying:

\(d(i,j)=d(j,k)=d(i,k)\),

where \(d(x,y)\) denotes the number of edges in the unique simple path connecting vertices \(x\) and \(y\) in the tree.

Note that triplets (i,j,k) and (i,k,j) are considered identical.

Hint: For any vertex considered as the center, if you look at its different branches (obtained by removing the center), then for a fixed distance \(L\) (\(L\ge1\)), if there are nodes reachable in at least three different branches at exactly distance \(L\), then any choice picking one node from each of three branches forms a valid triplet with pairwise distances \(2L\).

inputFormat

The first line contains an integer n (the number of vertices in the tree).

Each of the following n-1 lines contains two integers u and v indicating that there is an edge between vertices u and v.

outputFormat

Output a single integer representing the number of unordered triplets (i, j, k) such that each pair among i, j, k has the same distance.

sample

4
1 2
1 3
1 4

1