Стрибаючий мавпеня
Ви мисливець, який переслідує мавпу в лісі, намагаючись збити її своєю всесильною автоматичною гвинтівкою. Мавпа ховається десь за гілками одного з дерев, поза вашим полем зору. Ви можете прицілитися в одне з дерев і вистрілити; ваші кулі здатні пробити гілки і миттєво вбити мавпу, якщо вона знаходиться на цьому дереві. Якщо її там немає, мавпа скористається часом, який вам потрібен для перезарядки, і стрибне на сусіднє дерево, не помітивши вас. Вона ніколи не залишається на тому ж місці після пострілу. Ви хочете дізнатися, чи існує стратегія, яка дозволяє вам захопити мавпу напевно, незалежно від її початкового місця розташування та наступних стрибків. Якщо так, вам потрібно визначити найкоротшу послідовність пострілів, що гарантує це.
Рисунок 2
Як приклад, розгляньте ситуацію, коли в лісі є лише два сусідні дерева (ліва частина Рисунка 2). Тоді можна бути впевненим, що ви захопите мавпу, зробивши два постріли в одне й те ж дерево. Ваш перший постріл буде вдалим, якщо мавпа спочатку була там. В іншому випадку, мавпа була за іншим деревом і обов'язково переміститься, коли ви вистрілите вдруге.
Однак, залежно від форми лісу, може бути неможливо забезпечити перемогу. Один з прикладів цього - якщо є три дерева, всі з'єднані одне з одним (права частина Рисунка 2). Незалежно від того, куди ви прицілитеся, завжди є два можливих місця для мавпи в будь-який момент. (Зверніть увагу, що тут ми розглядаємо найгірший сценарій, коли мавпа може постійно вгадувати ваше наступне цільове дерево).
Вхідні дані
Вхід складається з декількох тестових випадків, розділених одним порожнім рядком. Кожен тестовий випадок починається з рядка, що містить два цілі числа n і m (1 ≤ n ≤ 21); n - це кількість дерев у лісі, а m - кількість відносин суміжності між деревами. Кожен з наступних m рядків містить два різних цілі числа від 0 до n-1 (включно), ідентифікатори дерев у суміжній парі. Порядок обох дерев у парі не має значення, і жодна пара не з'являється більше одного разу. Ви можете далі припустити, що жодне дерево не є суміжним із самим собою, і завжди існує шлях між будь-якими двома деревами в лісі.
Тестові випадки завершуються рядком, що містить лише два нулі (також передує порожній рядок).
Вихідні дані
Надрукуйте рядок для кожного тестового випадку. Рядок повинен містити одне слово 'Impossible', якщо завдання неможливе. В іншому випадку, він повинен містити найкоротшу послідовність пострілів з необхідною властивістю, у форматі L: V_1V_2...V_L, де L - це довжина послідовності, а V_1, V_2,..., V_L - це розділені пробілами цілі числа, що містять ідентифікатори дерев, в які потрібно стріляти у правильному порядку. Якщо існує кілька найкоротших послідовностей, надрукуйте лексикографічно найменшу. (Послідовність менша за іншу в лексикографічному порядку, якщо перший елемент, на якому вони відрізняються, менший у першій).