Недавно Витя приезжал на олимпиаду в Москву и удивился тому, как быстро можно путешествовать по городу на метро. В отличие от метро в его родном городе, в московском метро есть кольцевые ветки, из-за чего от одной станции до другой можно добираться несколькими разными маршрутами.

Метро в родном городе Вити состоит из $$$n$$$ станций, которые соединены $$$n - 1$$$ туннелями. Проезд по каждому туннелю занимает ровно одну минуту. Метро устроено так, что от одной станции до другой можно добраться ровно одним способом, если, конечно, не растягивать своё путешествие намеренно и не проезжать по одним и тем же туннелям по несколько раз. Другими словами, граф метро является деревом.

Вите стало интересно, как бы улучшилась работа метро в его городе, если бы в нём появилась хотя бы маленькая кольцевая ветка. Чтобы это узнать, он рассмотрит все пары станций метро $$$(u, v)$$$ в его городе, посчитает, сколько минут занимает кратчайший путь от $$$u$$$ до $$$v$$$, и просуммирует все результаты. После этого он добавит в метро один туннель так, чтобы в нём появился цикл длины ровно 3, и посчитает сумму расстояний ещё раз. При этом проезд по новому туннелю также будет занимать одну минуту. Он хочет провести туннель таким образом, чтобы новая сумма расстояний стала как можно меньше.

Рассмотрев пару вариантов, Витя устал считать суммы и попросил вас написать программу, которая найдёт ответ на его вопрос.