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