Сервера

Корпорация имеет n серверов, которые занумерованы натуральными числами от 1 до n. Каждый сервер занимает одну полку в серверной стойке. Всего в стойке n полок, и их также занумерованы натуральными числами от 1 до n. В связи с заменой оборудования возникла необходимость переставить серверы. Проблему затруднено тем, что некоторые пары серверов нужно соединить кабелем напрямую. Длина кабеля, соединяющего пару серверов, равна разнице номеров полок, на которых расположены эти серверы. Помогите разместить серверы так, чтобы суммарная длина затраченного кабеля была наименьшей. Определите, какое наименьшее суммарную длину кабеля нужно потратить для размещения серверов в серверной стойке и одно из возможных таких расположений.

Входные данные

Первая строка содержит натурально число n (2 ≤ n ≤ 20). Вторая строка содержит количество пар серверов m, которые следует соединить напрямую.

Следующие m строк содержат по одной паре разных натуральных чисел - номера серверов, которые следует соединить напрямую. Каждая такая перестановка встречается в перечне только один раз.

Выходные данные

В первой строке вывести наи­меньшую возможную суммарную длину кабеля. Во второй строке вывести перестановку чисел 1, 2, …, n, которая соответствует оптимальному расположению серверов: на j-ом месте должен стоять номер сервера, который следует установить на j-ой полке.

Примеры