Эта задача разбита на две. В данной задаче, вам нужно найти максимальный ответ. В задаче же Посёлок (Минимум) вам нужно найти минимальный возможный ответ. За каждую из этих задач можно получить по \(50\) баллов.
В одном посёлке люди живут в \(N\) домах. В каждом доме живёт ровно один житель. Дома соединены дорогами. Каждая дорога соединяет два дома и имеет длину \(1\) км. Из каждого дома можно достичь любой другой дом, идя по одной или нескольким дорогам. В общем в посёлке ровно \(N-1\) дорог.
Однажды все жители решили переехать в другие дома. После переезда всех жителей в каждом доме снова должен жить ровно один житель, но ни один житель не должен остаться в том же доме, в котором жил до этого. Наша цель — узнать наибольшую возможную сумму кратчайших путей (в км) перемещения всех жителей из старых мест жительства на новые.
Пример посёлка с семью домами
Например, если всего есть семь домов, соединённых дорогами так, как показано на рисунке, то наибольшая общая длина равняется \(18\) км (этого можно достичь, перемещая жителей \(1 \to 7\), \(2 \to 3\), \(3 \to 4\), \(4 \to 1\), \(5 \to 2\), \(6 \to 5\), \(7 \to 6\)).
Напишите программу, которая находит наибольшую возможную сумму кратчайших путей (в км), а также распределение жителей по новым домам.
Выходные данные
В первой строке выведите одно целое число, наибольшую возможную общую длину кратчайших путей жителей в километрах.
Во второй строке опишите одно правильное распределение жителей по новым домам с наибольшей возможной общей длиной: \(N\) различных целых чисел \(v_1, v_2, \ldots, v_N\). Для каждого \(i\), \(v_i\) обозначает номер дома, в который должен переехать житель из дома с номером \(i\) (\(v_i \neq i\)). Если существует несколько распределений, выведите любое из них.