Shymbulak#7471
At the famous Kazakh resort of Shymbulak, there are scenic vacation spots connected by trails of equal length. Each trail can be used to travel in both directions. The network of trails is arranged in such a way that it is possible to get from any spot to any other. However, in some cases, the number of transfers required may be quite large.
Before constructing new trails, the resort administration wants to determine how many different shortest paths exist between all pairs of vacation spots that are the farthest apart.
By spots that are the farthest apart, we mean such pairs of spots for which the length of the shortest path (in number of trails) is maximized. The output should be the total number of shortest paths between all such pairs.
The first line contains an integer n~(3 \le n \le 200,000). Each of the next lines contains two integers — the indices of vacation spots connected by a corresponding trail. It is guaranteed that each trail connects two distinct spots and that the entire network is connected.
Output a single integer — the number of shortest paths between all pairs of vacation spots that are the farthest apart.
In the first example, the most distant pairs of spots are and . There are two different shortest paths between each of these pairs, so the answer is .
Esempio 1
Esempio 2