Space competition#2556
planets are located in sector E4 of the Omicron Theta area. Ageira Technologies has completely monopolized space transportation by building a network of Trade Lines.
Each Trade Line is a two-way portal between a pair of planets. Ageira Technologies, taking advantage of the economic situation, built a minimal number of Trade Lines so that it is possible to travel from each planet to any other planet by using some of the Trade Lines. Exactly N - 1 Trade Lines were built.
Many residents of distant planets are unhappy with this situation, because to get from one planet to another, they have to use many Trade Lines. The longer the journey, the greater the danger of encountering space pirates!
Nomad Industries, a rival company, wants to take advantage of this situation and build its own network of Hyper Gates in the sector to capture part of the space transportation market. Nomad Industries’ specialists have determined that the profit from building a Gate between planets and is equal to the length of the path between those planets that must be traversed using only Ageira's Trade Lines. The length of the path between planet and planet is defined as the minimal number of Trade Lines used to get from to .
Nomad Industries has decided to act by analogy to Ageira’s policy: to build a minimal number of Gates such that it is possible to travel from each planet to any other planet without using Trade Lines at all.
Write a program to find a configuration of the Gates that results in the maximum total profit from all built Gates. (Note that exactly N - 1 Gates must be built)
The first line of input contains an integer (2 \leq N \leq 2000), the number of planets in the sector. The next N - 1 lines each contain two integers separated by a space, denoting the identifiers of planets connected by Ageira Technologies’ Trade Lines. The identifiers of planets are unique integers from to .
The output should contain a single integer — the maximum possible profit for Nomad Industries.
Example 1