Shymbulak
Shymbulak
On the famous kazakh resort Shymbulak there are n interesting places for tourists, which are connected by n roads of equal length. Roads are bidirectional. The road system is constructed in such way that from any place you can reach any other place, but sometimes it takes too many steps. Before adding new roads the resort administration wants to know, how many paths are there between all pairs of places which situated farthest apart from each other.
Pairs of places which situated farthest apart from each other means such pairs of places that the shortest path between them is maximal. The answer you should calculate is the total number of shortest paths between all pairs of places that satisfy the condition above.
Input
The first line contains integer n (3 ≤ n ≤ 200 000). Each of the next n lines contains 2 integers - numbers of places, which are connected by a road. It is guaranteed that all roads connect different pairs of places.
Output
Output one integer - a number of shortest paths between all pairs of places which situated farthest apart from each other.
6 1 2 1 3 2 4 4 3 4 5 4 6
4
4 1 2 1 3 1 4 4 3
2
Example description: In the first example farthest apart places are 1, 5 and 1, 6. For every pair there are two different paths. So the answer is 4.