Сервери

Корпорація має N серверів, які занумеровано натуральними числами від 1 до N. Кожен сервер займає одну полицю в серверній стійці. Всього в стійці N полиць, і їх також занумеровано натуральними числами від 1 до N. У зв’язку з заміною обладнання виникла потреба переставити сервери. Проблему ускладнено тим, що деякі пари серверів потрібно з’єднати кабелем напрямý. Довжина кабелю, що з’єднує пару серверів, дорівнює різниці номерів полиць, на яких розташовані ці сервери. Допоможіть розмістити сервери так, щоб сумарна довжина затраченого кабелю була найменшою.

Визначте, яку найменшу сумарну довжину кабелю потрібно витратити для роз­ташу­вання серверів у серверній стійці та одне з можливих таких розташувань.

Вхідні дані

Перший рядок містить натуральне число N (2 ≤ N ≤ 20). Другий рядок містить кількість пар M серверів, що потрібно з’єднати напряму.

Наступні M рядків містять по одній парі різних натуральних чисел — номери серверів, що потрібно з’єднати напрямý. Кожна така пара зустрічається у переліку лише один раз.

Вихідні дані

Перший рядок повинен містити най­меншу можливу сумарну довжину кабелю. Другий рядок повинен містити перестановку чисел 1, 2, …, N, що відповідає оптимальному розташуванню серверів: на j-му місці має стояти номер сервера, який потрібно встановити на j-ту полицю.

Приклади