Сервери#7065
Корпорація має серверів, які занумеровано натуральними числами від до . Кожен сервер займає одну полицю у серверній шафі. Всього в шафі полиць, і їх також занумеровано натуральними числами від до . У зв'язку із заміною обладнання виникла потреба переставити сервери. Проблему ускладнено тим, що деякі пари серверів потрібно з'єднати кабелем напряму. Довжина кабелю, що з'єднує пару серверів, дорівнює різниці номерів полиць, на яких розташовані ці сервери.
Допоможіть розмістити сервери так, щоб сумарна довжина витраченого кабелю була найменшою.
Визначте найменшу можливу сумарну довжину кабелю та одне з можливих розташувань серверів.
Перший рядок містить натуральне число (2 \le N \le 20). Другий рядок містить кількість пар серверів , які потрібно з'єднати напряму.
Наступні рядків містять по одній парі різних натуральних чисел — номери серверів, які потрібно з'єднати напряму. Кожна така пара зустрічається у переліку лише один раз.
Перший рядок повинен містити найменшу можливу сумарну довжину кабелю. Другий рядок повинен містити перестановку чисел 1, 2, \ldots, N, що відповідає оптимальному розташуванню серверів: на -му місці має стояти номер сервера, який потрібно встановити на -ту полицю.
Приклад 1