eolymp
bolt
Try our new interface for solving problems
Problems

Space competition

Space competition

Time limit 3 seconds
Memory limit 64 MiB

N planets are situated in the sector E4 of the Omicron Theta area. And it just so happened that the Ageira Technologies company 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 one could get from each planet i to any other planetj , using some of Trade Lines. There are n-1 Trade Lines built by Ageira.

Many residents of distant planets were unhappy with such situation, because to get from one planet to another, they have to use a lot of Trade Lines. And the longer the journey, the greater the danger to meet space pirates!

Nomad Industries company, the rival of Ageira company, wants to take advantage of the situation and build in the sector theirs own network of Hyper Gates to capture part of the market of space transportation. Qualified specialists of Nomad Industries has found out that profit from building the Gate between planets i and j will be equal to the length of the path that must be overcome by using only Ageira‘s Trade Lines. By length of the path between planet i and planet j we mean the minimal number of Trade Lines used to get from planet i to planet j.

Nomad Industries has decided to act on the principle similar to Ageira’s policy: to build a minimal amount of the Gates in such a way that one could get from each planet i to any other planet j, not using the Trade Lines at all.

Write program, that will find such Gate configuration, which has a maximal resulting profit of all gates built. (Note, that company should build exactly N-1 Gates)

Input data

The first line of input file consists of an integer N (2N2000) – the number of planets in the sector and the number of Trade Lines, respectively. First line is followed by N-1 lines, each contains two numbers separated by a space – planets’ identifiers, connected by Ageira Technologies’ Trade Lines. Identifiers of planets are the unique integers from 1 to N.

Output data

The first line of output file should contain single integer – the maximal profit of Nomad Industries company.

Examples

Input example #1
6
1 3
2 3
3 4
4 5
4 6
Output example #1
13