eolymp
bolt
Try our new interface for solving problems
Məsələlər

Сервера

Сервера

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 32 MiB

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

Giriş verilənləri

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

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

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
5
3
1 2
2 3
4 5
Çıxış verilənləri #1
3
5 4 1 2 3