На другом этаже A.R.C. Markland-N, молодой человек Саймон "Ксенон" Джексон отдыхает, завершив свои работы по проекту быстрее запланированного (впрочем как всегда). Так как свободного времени достаточно много, он надевает свой легендарный хакерский "X" инстинкт и бежит сражаться против банд кибермира.
Его целью является сеть из \(n\) небольших банд. Их сеть состоит из ровно \(n - 1\) прямых соединений, каждое из которых связывает какие-то две банды вместе. Соединения устроены таким образом, что любые две банды соединены через последовательность прямых соединений.
Изучая данные, Ксенон понял, что банды используют для самозащиты следующую форму шифрования. Каждому соединению назначено целое число от \(0\) до \(n - 2\), таким образом, что все назначенные числа различны, а каждое число назначено какому-то соединению. Если атакующий пытается получить доступ к защищённым данным, то ему придётся прорваться через \(S\) слоёв с паролями, где \(S\) определяется как:
\(\)S = \sum_{1 \leq u < v \leq n} mex(u, v)\(\)
Здесь \(mex(u, v)\) обозначает наименьшее неотрицательное целое число, которое не встречается на соединениях на единственном простом пути между бандами \(u\) и \(v\).
Ксенон не знает каким образом числа были назначены соединениям, но это не проблема. Он собирается поручить своим AI перебрать и взломать все пароли, но перед этим он хочет знать чему равно наибольшее возможное значение \(S\), чтобы настроить AI наиболее эффективно.
Сейчас Ксенон ушёл писать скрипты для AI, и он собирается их закончить в течение двух часов. Не могли бы вы найти наибольшее значение \(S\) перед тем, как он вернётся?
Примечание
В первом примере можно достичь максимального \(S\) следующим образом:
В этой сети, \(mex(1, 2) = 0\), \(mex(1, 3) = 2\) и \(mex(2, 3) = 1\). Таким образом, \(S = 0 + 2 + 1 = 3\).
Во втором примере можно достичь максимального \(S\) таким образом:
В этой сети все ненулевые значения mex перечислены ниже:
- \(mex(1, 3) = 1\)
- \(mex(1, 5) = 2\)
- \(mex(2, 3) = 1\)
- \(mex(2, 5) = 2\)
- \(mex(3, 4) = 1\)
- \(mex(4, 5) = 3\)
Таким образом, \(S = 1 + 2 + 1 + 2 + 1 + 3 = 10\).