A13236 | Xenon's Attack on the Gangs

[INSPION FullBand Master - INSPION](https://www.youtube.com/watch?v=kwsciXm_7sA)



[INSPION - IOLITE-SUNSTONE](https://www.youtube.com/watch?v=kwsciXm_7sA)



On another floor of the A.R.C. Markland-N, the young man Simon "Xenon" Jackson, takes a break after finishing his project early (as always). Having a lot of free time, he decides to put on his legendary hacker "X" instinct and fight against the gangs of the cyber world.

His target is a network of $n$ small gangs. This network contains exactly $n - 1$ direct links, each of them connecting two gangs together. The links are placed in such a way that every pair of gangs is connected through a sequence of direct links.

By mining data, Xenon figured out that the gangs used a form of cross-encryption to avoid being busted: every link was assigned an integer from $0$ to $n - 2$ such that all assigned integers are distinct and every integer was assigned to some link. If an intruder tries to access the encrypted data, they will have to surpass $S$ password layers, with $S$ being defined by the following formula:

$$$$S = \sum_{1 \leq u < v \leq n} mex(u, v) $$ </p><p>Here, $mex(u, v)$ denotes the smallest non-negative integer that does not appear on any link on the unique simple path from gang $u$ to gang $v$ .</p><p>Xenon doesn't know the way the integers are assigned, but it's not a problem. He decides to let his AI's instances try all the passwords on his behalf, but before that, he needs to know the maximum possible value of $S$ , so that the AIs can be deployed efficiently.</p><p>Now, Xenon is out to write the AI scripts, and he is expected to finish them in two hours. Can you find the maximum possible $S$$$ before he returns?

The first line contains an integer $n$ ( $2 \leq n \leq 3000$ ), the number of gangs in the network.

Each of the next $n - 1$ lines contains integers $u_i$ and $v_i$ ( $1 \leq u_i, v_i \leq n$ ; $u_i \neq v_i$ ), indicating there's a direct link between gangs $u_i$ and $v_i$ .

It's guaranteed that links are placed in such a way that each pair of gangs will be connected by exactly one simple path.

Print the maximum possible value of $S$ — the number of password layers in the gangs' network.