Equidistant Hotel Triplets

Byteasar, the king of Byteotia, wants to attract tourists by erecting three luxury hotels in different towns. Byteotia has n towns connected by n-1 two‐way roads, forming a tree (i.e. a connected acyclic graph). All roads have the same length. The king desires that the hotels be located in three different towns so that the pairwise distances between any two hotels are equal. Note that if the common distance is 2k (for some positive integer k), then there exists a town acting as a center, from which each hotel is exactly at distance k and the three hotels lie in three distinct branches emanating from that center.

Your task is to determine the number of possible hotel triplets.

Hint: In any tree, if such an equidistant triple exists then the common distance must be even; the three hotels will always be located at distance k from some central town, so that the distance between any two hotels is 2k.

inputFormat

The input consists of several lines. The first line contains an integer n (with n ≥ 3), the number of towns. Each of the following n-1 lines contains two integers u and v (1 ≤ u, v ≤ n), indicating that there is a road between towns u and v. It is guaranteed that the network forms a tree.

outputFormat

Output a single integer: the number of triplets of towns which satisfy the condition that the distances between every pair of the three towns are equal.

sample

4
1 2
2 3
2 4

1